1 条题解
-
4
C++ :
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; #define ll long long const int maxn=7000000+10; const ll inf=1ll<<60; int m,n,q,t,tmp; int qu[3][maxn],head[3],tail[3];//维护三个单调队列 ll u,v; bool Cmp(int a,int b){ return a>b; } void Init(){ scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t); for(int i=1;i<=n;i++){ scanf("%d",&qu[0][i]); } sort(qu[0]+1,qu[0]+1+n,Cmp); tmp=0; head[0]=head[1]=head[2]=1; tail[0]=n;//一开始所有蚯蚓都在第1队列里,我们把px都放入第2队列,x-px都放入第3队列 tail[1]=tail[2]=0; } void Solve(){ ll now; int from,l1,l2,out=0; bool flag=1; for(int i=1;i<=m;i++){ now=-inf;//选取三个队列中的最大值 from=-1; for(int j=0;j<=2;j++) if(head[j]<=tail[j]){ if(qu[j][head[j]]>now){//更新最大值 now=qu[j][head[j]]; from=j; } } now+=tmp; out++; if(out==t){//保证在t的整数倍输出 if(!flag) printf(" "); flag=0; printf("%lld",now); out=0; } l1=now*u/v; l2=now-l1; head[from]++; tmp+=q; l1-=tmp,l2-=tmp; qu[1][++tail[1]]=l1;//添加队列元素 qu[2][++tail[2]]=l2; //printf("after %d s cut,tmp=%d\n",i,tmp); } printf("\n"); //以下为第二行输出 m+=n;out=0;flag=true; for(int i=1;i<=m;i++) { now=-inf; from=-1; for(int j=0;j<3;j++) if(head[j]<=tail[j]){ if(qu[j][head[j]]>now){ now=qu[j][head[j]]; from=j; } } now+=tmp; out++; if(out==t) { if(!flag) printf(" "); flag=false; printf("%lld",now); out=0; } head[from]++; } } int main(){ Init(); Solve(); return 0; }
- 1
信息
- ID
- 44
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 4
- 标签
- 递交数
- 108
- 已通过
- 47
- 上传者