题目：https://www.luogu.org/problemnew/show/P2827
一眼看到优先队列。可是会被卡吧。
结果没想出来。
优先队列的复杂度在于不停排序。本题的q和p等都是定值。如果能找到什么性质（单调的）避免排序就好了。
需要分析。x>y，先切x再切y的话，x*p+q>y*p+q*p，对于1-p的部分也是一样。
即切出来的部分有单调性。所以再开两个队列存 *p的部分 和 *(1-p)的部分 就行了。
注意还要加上q。记录一个入队时间（弄弄边界）即可。
自己需要分析。列出式子之类的。明确自己要找的是什么（本题：单调性）。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const int N=1e5+5,M=7e6+5; const ll INF=0x7fffffff; int n,m,s,u,v,T,tim[5][N+M],h[5],t[5]; ll q[5][N+M]; bool cmp(ll a,ll b){return a>b;} int rdn() { int ret=0,fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')fx=-1;ch=getchar();} while(ch>='0'&&ch<='9')(ret*=10)+=ch-'0',ch=getchar(); return ret*fx; } int main() { n=rdn();m=rdn();s=rdn();u=rdn();v=rdn();T=rdn(); for(int i=1;i<=n;i++)q[0][i]=rdn(),tim[0][i]=1; sort(q[0]+1,q[0]+n+1,cmp); h[0]=1;t[0]=n;h[1]=1;h[2]=1; for(int i=1;i<=m;i++) { int k=-1;ll mx=0; if(h[0]<=t[0]&&q[0][h[0]]+s*(i-tim[0][h[0]])>mx) k=0,mx=q[0][h[0]]+s*(i-tim[0][h[0]]); if(h[1]<=t[1]&&q[1][h[1]]+s*(i-tim[1][h[1]])>mx) k=1,mx=q[1][h[1]]+s*(i-tim[1][h[1]]); if(h[2]<=t[2]&&q[2][h[2]]+s*(i-tim[2][h[2]])>mx) k=2,mx=q[2][h[2]]+s*(i-tim[2][h[2]]); h[k]++;if(i%T==0)printf("%lld ",mx); q[1][++t[1]]=mx*u/v;tim[1][t[1]]=i+1; q[2][++t[2]]=mx-mx*u/v;tim[2][t[2]]=i+1; // for(int i=0;i<3;i++)for(int j=h[i];j<=t[i];j++)printf("q[%d][%d]=%lld,tim=%d ",i,j,q[i][j],tim[i][j]); } printf(" "); for(int i=1;i<=n+m;i++) { int k=-1;ll mx=0; if(h[0]<=t[0]&&q[0][h[0]]+s*(m-tim[0][h[0]]+1)>mx) k=0,mx=q[0][h[0]]+s*(m-tim[0][h[0]]+1); if(h[1]<=t[1]&&q[1][h[1]]+s*(m-tim[1][h[1]]+1)>mx) k=1,mx=q[1][h[1]]+s*(m-tim[1][h[1]]+1); if(h[2]<=t[2]&&q[2][h[2]]+s*(m-tim[2][h[2]]+1)>mx) k=2,mx=q[2][h[2]]+s*(m-tim[2][h[2]]+1); h[k]++;if(i%T==0)printf("%lld ",mx); } return 0; }