题目描述

本题中，我们将用符号 \lfloor c \rfloor⌊c⌋ 表示对 cc 向下取整，例如：\lfloor 3.0 \rfloor = \lfloor 3.1 \rfloor = \lfloor 3.9 \rfloor = 3⌊3.0⌋=⌊3.1⌋=⌊3.9⌋=3。

蛐蛐国最近蚯蚓成灾了！隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。

蛐蛐国里现在共有 nn 只蚯蚓（nn 为正整数）。每只蚯蚓拥有长度，我们设第 ii 只蚯蚓的长度为 a_iai​ (i=1,2,\dots,ni=1,2,…,n)，并保证所有的长度都是非负整数（即：可能存在长度为 00 的蚯蚓）。

每一秒，神刀手会在所有的蚯蚓中，准确地找到最长的那一只（如有多个则任选一个）将其切成两半。神刀手切开蚯蚓的位置由常数 pp（是满足 0 < p < 10<p<1 的有理数）决定，设这只蚯蚓长度为 xx，神刀手会将其切成两只长度分别为 \lfloor px \rfloor⌊px⌋ 和 x - \lfloor px \rfloorx−⌊px⌋ 的蚯蚓。特殊地，如果这两个数的其中一个等于 00，则这个长度为 00 的蚯蚓也会被保留。此外，除了刚刚产生的两只新蚯蚓，其余蚯蚓的长度都会增加 qq（是一个非负整常数）。

蛐蛐国王知道这样不是长久之计，因为蚯蚓不仅会越来越多，还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物，但是救兵还需要 mm 秒才能到来……（mm 为非负整数）

蛐蛐国王希望知道这 mm 秒内的战况。具体来说，他希望知道：

• mm 秒内，每一秒被切断的蚯蚓被切断前的长度（有 mm 个数）；
• mm 秒后，所有蚯蚓的长度（有 n + mn+m 个数）。

蛐蛐国王当然知道怎么做啦！但是他想考考你……

 

 不论是手写堆还是STL的优先队列，你都逃不过TLE的好成绩。

// luogu-judger-enable-o2#include
     
      #define N 51000110using namespace std;int n,m,q,u,v,t,size,fq,heap[N];double p;//priority_queue
      
       
         >Q;struct node{    void push(int x){        int now,next;        heap[++size]=x;        now=size;        while(now>1){            next=now>>1;            if(heap[next]>=heap[now]) break;            swap(heap[next],heap[now]);            now=next;        }    }    int top(){        int now=1,next,ans;        ans=heap[1];        heap[1]=heap[size--];        while(now*2<=size){            next=now*2;            if(next
        
         heap[next]) next++;            if(heap[now]>heap[next]) break;            swap(heap[now],heap[next]);            now=next;        }return ans;    }}Q;int main() {    scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);    p=(double)u/v;    for(int x,i=1; i<=n; i++) {        scanf("%d",&x);        Q.push(x);    }    for(int i=1; i<=m; i++) {        int top=Q.top();        top+=fq;        if(i%t==0) printf("%d ",top);        int a=top*p,b=top-a;        fq+=q;        a-=fq,b-=fq;        Q.push(a);        Q.push(b);    }//    printf("%d\n",size);    puts("");    for(int i=1;i<=n+m;i++){        int an=Q.top();        an+=fq;        if(i%t==0) printf("%d ",an);    }    return 0;}
        
       
      
     

 

 仔细观察一下，你就会发现隐含的单调性，假设先被切掉的为$x$,后被切掉的为$y$,那么$x$分成的$x1=px+q$,$x2=x-px+q$,$y$分成的$y1=p*(y+q)$,$y2=y-p*(y+q)$

　$x1>=y1$ ,$x2>=y2$

那么本身分成的这两堆就具有一定的单调性

即：$x1>y1>z1>...$,$x2>y2>z2>...$

 

那么就可以模拟了，每次取三个堆中的最大值即可

 

#include
     
      #include
      
       #include
       
        #define N 14010100using namespace std;int n,m,q,u,v,t,Q[3][N];double p;bool cmp(int x,int y){    return x>y;}int main() {//    freopen("2827.in","r",stdin);//    freopen("2827.out","w",stdout);    scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);    p=(double)u/v;        for(int i=0;i<=n+1;i++) Q[0][i]=Q[1][i]=Q[2][i]=-0x7fffffff;        for(int i=1; i<=n; i++) scanf("%d",&Q[0][i]);    sort(Q[0]+1,Q[0]+1+n,cmp);        int top_1,top_2,top_3,fq=0,tail_2,tail_3;    top_1=top_2=top_3=1;    tail_2=tail_3=0;        for(int i=1; i<=m; i++) {        int top=-0x7fffffff;        if(top_1<=n) top=max(Q[0][top_1],top);        if(top_2<=tail_2) top=max(Q[1][top_2],top);        if(top_3<=tail_3) top=max(Q[2][top_3],top);                 if(top==Q[0][top_1]&&top_1<=n) top_1++;        else if(top==Q[1][top_2]&&top_2<=tail_2) top_2++;        else top_3++;                top+=fq;        if(i%t==0) printf("%d ",top);        int a=top*p,b=top-a;        fq+=q;        a-=fq,b-=fq;        Q[1][++tail_2]=b;        Q[2][++tail_3]=a;    }    puts("");        for(int i=1;i<=n+m;i++){        int top=-0x7fffffff;        if(top_1<=n) top=max(Q[0][top_1],top);        if(top_2<=tail_2) top=max(Q[1][top_2],top);        if(top_3<=tail_3) top=max(Q[2][top_3],top);                 if(top==Q[0][top_1]&&top_1<=n) top_1++;        else if(top==Q[1][top_2]&&top_2<=tail_2) top_2++;        else top_3++;                if(i%t==0) printf("%d ",top+fq);    }        return 0;}