傳送門

解題思路

第一眼以為是一個二叉堆，直接上優先隊列60分。。。后來聽ztz11說有單調性，新加入的蚯蚓一定比原先在的蚯蚓長度長，開三個隊列，分別放原先的長度，切掉后大的那一半，切掉后小的那一半。假設原先的第一個數為x1，第二個數為x2，x1>x2，那么取出x1后大的那一半記做x1*p（假設p>1/2) ，第二個數此時加q，第二次再將第二個數拿出來，大的那一半就是(x2+q)*p=x2*p+q*p，而原先第一個數大的那一半變成了x1*p+q，因為x1>x2，p<0，所以符合單調性。所以只需要每次取出最大的切，然后分成兩半分別放入第二個與第三個隊列。

代碼

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue>typedef long long LL; using namespace std; const int MAXN = 1e5+5; const LL inf = 1e18+5; const int MAXM = 7e6+5;inline int rd(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f; }int n,m,q,u,v,t; LL ans[MAXM],a[MAXN]; queue<LL> Q[4];inline bool cmp(int x,int y){return x>y; }int main(){ // freopen("rand.txt","r",stdin); // freopen("A.txt","w",stdout);n=rd();m=rd();q=rd();u=rd();v=rd();t=rd();for(register int i=1;i<=n;i++) a[i]=rd();sort(a+1,a+1+n,cmp);for(register int i=1;i<=n;i++) Q[1].push(a[i]);for(register int i=1;i<=m;i++){LL x=-inf,y=-inf,z=-inf;if(Q[1].size()) x=Q[1].front();if(Q[2].size()) y=Q[2].front();if(Q[3].size()) z=Q[3].front(); LL mx=x;int r=1;if(y>mx) mx=y,r=2;if(z>mx) mx=z,r=3;Q[r].pop();mx+=(LL)(i-1)*q;ans[i]=mx;LL now=mx;mx=mx*u/v;now=now-mx;Q[2].push(max(now,mx)-(LL)i*q);Q[3].push(min(now,mx)-(LL)i*q);}for(register int i=t;i<=m;i+=t) printf("%lld ",ans[i]);puts("");int yy=1;for(register int i=1;i<=n+m;i++){LL x=-inf,y=-inf,z=-inf;if(Q[1].size()) x=Q[1].front();if(Q[2].size()) y=Q[2].front();if(Q[3].size()) z=Q[3].front(); LL mx=x;int r=1;if(y>mx) mx=y,r=2;if(z>mx) mx=z,r=3;Q[r].pop(); // cout<<mx+(LL)q*m<<" ";if(yy<t) {yy++;continue;}yy=1;printf("%lld ",mx+(LL)m*q);}return 0; }

轉載于:https://www.cnblogs.com/sdfzsyq/p/9676922.html

總結

以上是生活随笔為你收集整理的LUOGU P2827 蚯蚓 (noip 2016)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。