P2827 蚯蚓
题目描述
本题中，我们将用符号 lfloor c floor⌊c⌋ 表示对 cc 向下取整，例如：lfloor 3.0 floor = lfloor 3.1 floor = lfloor 3.9 floor = 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 floor⌊px⌋ 和 x - lfloor px floorx−⌊px⌋ 的蚯蚓。特殊地，如果这两个数的其中一个等于 00，则这个长度为 00 的蚯蚓也会被保留。此外，除了刚刚产生的两只新蚯蚓，其余蚯蚓的长度都会增加 qq（是一个非负整常数）。
蛐蛐国王知道这样不是长久之计，因为蚯蚓不仅会越来越多，还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物，但是救兵还需要 mm 秒才能到来……（mm 为非负整数）
蛐蛐国王希望知道这 mm 秒内的战况。具体来说，他希望知道：
- mm 秒内，每一秒被切断的蚯蚓被切断前的长度（有 mm 个数）；
- mm 秒后，所有蚯蚓的长度（有 n + mn+m 个数）。
蛐蛐国王当然知道怎么做啦！但是他想考考你……
不论是手写堆还是STL的优先队列，你都逃不过TLE的好成绩。
// luogu-judger-enable-o2 #include<bits/stdc++.h> #define N 51000110 using namespace std; int n,m,q,u,v,t,size,fq,heap[N]; double p; //priority_queue<int,vector<int> >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<size&&heap[next+1]>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 ",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<iostream> #include<cstdio> #include<algorithm> #define N 14010100 using 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; }