1 条题解

  • 4
    @ 2021-8-7 20:34:55

    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
    上传者