好题。
目测只会多带一个log2(n+m)” role=”presentation” style=”position: relative;”>log2(n+m)log2(n+m)的解法,看了题解之后才会正解。
解析:
我们用三个队列来维护每次弹出的值。
第一个队列就是原数列。
第二个队列是每次砍掉后短的那一节组成的,第三个队列是长的那一节组成的。
显然这三个队列都具有单调性。
那么每次从三个队列中选一个最大的然后压入后两个队列里就行了。
实现细节见代码吧。
代码:
#include<bits/stdc++.h>#define N 7000005#define ll long longusing namespace std;inline int read(){ int ans=0; char ch=getchar(); while(!isdigit(ch))ch=getchar(); while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar(); return ans;}inline void write(int x){ if(x>9)write(x/10); putchar((x%10)^48);}inline bool cmp(const int&a,const int&b){return a>b;}int q[3][N],n,m,Q,t,u,v,hd[3],tl[3],tmp,delta=0;inline int calc(){ int pos,ret=-2147483647; for(int i=0;i<3;++i)if(hd[i]<tl[i]&&q[i][hd[i]+1]>ret)pos=i,ret=q[i][hd[i]+1]; ++hd[pos]; return ret;}int main(){ n=read(),m=read(),Q=read(),u=read(),v=read(),t=read(); for(int i=1;i<=n;++i)q[0][++tl[0]]=read(); sort(q[0]+1,q[0]+n+1,cmp); for(int i=1;i<=m;++i){ int tmp=calc()+delta; if(i%t==0)write(tmp),putchar(i+t>m?'\n':' '); int shor=(long long)tmp*u/v,lon=tmp-shor; delta+=Q,q[1][++tl[1]]=shor-delta,q[2][++tl[2]]=lon-delta; } if(t>m)puts(""); for(int i=1;i<=n+m;++i){ int tmp=calc()+delta; if(i%t==0){write(tmp);if(i+t<=n+m)putchar(' ');} } return 0;}