#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=100004,maxm=7000004;
int n,m,q,u,v,t;
int a[maxn],b[maxm],c[maxm];
bool cmp(int x,int y){
    if(x>y) return true;
    return false;
}
int main(){
    //freopen("earthworm.in","r",stdin);
    //freopen("earthworm.out","w",stdout);
    scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
    double p=double(u*1.0/v);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+n+1,cmp);
    int zc=0,l1=1,l2=1,r2=0,l3=1,r3=0;
    for(int i=1;i<=m;i++){
        int x=-999999999,y=-999999999,z=-999999999;
        if(l1<=n) x=a[l1];
        if(l2<=r2) y=b[l2];
        if(l3<=r3) z=c[l3];
        int w=max(x,max(y,z));
        if(w==x) l1++;
        else if(w==y) l2++;
        else l3++;
        x=w;
        x+=zc;
        int q1=floor(x*p*1.0);
        int q2=x-q1;
        q1-=zc;q2-=zc;
        q1-=q,q2-=q;
        b[++r2]=q1,c[++r3]=q2;
        if(i%t==0) printf("%d ",x);
        zc+=q;
    }
    printf("\n");
    for(int i=1;i<=n+m;i++){
        int x=-999999999,y=-999999999,z=-999999999;
        if(l1<=n) x=a[l1];
        if(l2<=r2) y=b[l2];
        if(l3<=r3) z=c[l3];
        int w=max(x,max(y,z));
        if(w==x) l1++;
        else if(w==y) l2++;
        else l3++;
        if(i%t==0) printf("%d ",w+zc);
    }
}

http://blog.csdn.net/jackypigpig/article/details/70196695

洛谷上的评测需要卡卡常

本质上是个单调队列，但是要是用自带的queue会超时，通过一些推理可以将其转化为普通的队列。
具体可以看看我的博客 ^w^

#include <cstdio>
#include <algorithm>
#define AA(x) (a[x]+(i-1)*q)
#define BB(x) (b[x]+(i-1)*q)
#define CC(x) (c[x]+(i-1)*q)
#define Max(x,y,z) max(x,max(y,z))
using namespace std;
long long n,m,q,u,v,t,k,k1,k2;
long long a[100005],b[7000005],c[7000005],A=1,B=1,C=1,rb,rc;
bool cmp(int x,int y){return x>y;}

long long Getk(int i){
    long long x1,x2,x3,xx;
    x1=x2=x3=-1;
    if (A<=n) x1=AA(A);
    if (B<=rb) x2=BB(B);
    if (C<=rc) x3=CC(C);
    xx=max(x1,max(x2,x3));
    if (xx==x1){A++; return x1;}
    if (xx==x2){B++; return x2;}
    else {C++; return x3;}
}

int main(){
    scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&q,&u,&v,&t);
    for (int i=1; i<=n; i++) scanf("%lld",&a[i]);
    sort(a+1,a+n+1,cmp);
    for (int i=1; i<=m; i++){
        k=Getk(i);
        if (i%t==0) printf("%lld ",k);
        k1=k*u/v, k2=min(k1,k-k1), k1=k-k2;
        b[++rb]=k1-i*q;
        c[++rc]=k2-i*q;
    }
    printf("\n");
    for (int i=1; i<=n+m; i++){
        k=Getk(m+1);
        if (i%t==0) printf("%lld ",k);
    }
    return 0;
}

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
using namespace std;

long long n,m,q,u,v,t;
deque<long long> dq_1;
deque<long long> dq_2;
deque<long long> dq_3;

void c_v_q_1()
{
    dq_1.resize(0);
    dq_2.resize(0);
    dq_3.resize(0);
}

bool cmp_1(long long x,long long y)
{
    return x>y;
}

void f_n_1(long long now_t,long long *now_l_p,long long *now_dq_p)
{
    *now_l_p=(numeric_limits<long long>::min)(),*now_dq_p=0;
    if (dq_1.size()>0)
        if (*now_l_p<dq_1.front())
            *now_l_p=dq_1.front(),*now_dq_p=1;
    if (dq_2.size()>0)
        if (*now_l_p<dq_2.front())
            *now_l_p=dq_2.front(),*now_dq_p=2;
    if (dq_3.size()>0)
        if (*now_l_p<dq_3.front())
            *now_l_p=dq_3.front(),*now_dq_p=3;
    *now_l_p+=(now_t-1)*q;
}

void p_dq_b_1(long long now_dq)
{
    if (now_dq==1)
        dq_1.pop_front();
    else if (now_dq==2)
        dq_2.pop_front();
    else if (now_dq==3)
        dq_3.pop_front();
}

int main()
{
    while (~scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&q,&u,&v,&t))
    {
        c_v_q_1();
        dq_1.resize(n,0);
        for (long long i=0;i<n;i++)
            scanf("%lld",&dq_1[i]);
        sort(dq_1.begin(),dq_1.end(),cmp_1);
        for (long long i=1;i<=m;i++)
        {
            long long now_l,now_dq;
            f_n_1(i,&now_l,&now_dq);
            dq_2.push_back((now_l*u/v)-(i*q));
            dq_3.push_back(now_l-dq_2.back()-(2*i*q));
            p_dq_b_1(now_dq);
            if (i%t==0)
                printf("%lld ",now_l);
        }
        printf("\n");
        for (long long i=1;i<=n+m;i++)
        {
            long long now_l,now_dq;
            f_n_1(m+1,&now_l,&now_dq);
            p_dq_b_1(now_dq);
            if (i%t==0)
                printf("%lld ",now_l);
        }
        printf("\n");
    }
}

单调队列233
考场码错了QAQ
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<ctime>
using namespace std;
int my_comp(int a,int b)
{
if(a>b) return 1;
return 0;
}
int d1[9*1000000],d2[9*1000000],d3[9*1000000];
int main()
{
int n,m,q,u,v,t,i,j,t1,l1,l2,l3;

//freopen("earthworm.in","r",stdin);
//freopen("earthworm.ans","w",stdout);

memset(d1,-128,sizeof(d1));
memset(d2,-128,sizeof(d2));
memset(d3,-128,sizeof(d3));

scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);

l1=l2=l3=1;

for(i=1;i<=n;i++)
scanf("%d",&d1[i]);

t1=t;

sort(d1+1,d1+n+1,my_comp);

for(i=1;i<=m;i++)
{
long long x1,x2,c,q1=d1[l1],q2=d2[l2],q3=d3[l3];
if(q1>=q2&&q1>=q3) {x1=d1[l1];l1++;}
else
{
if(q2>=q1&&q2>=q3) {x1=d2[l2];l2++;}
else {x1=d3[l3];l3++;}
}

long long a=(x1+=(i-1)*q)*u/v;

d2[i]=a-i*q;
d3[i]=x1-a-i*q;

if(i%t==0) printf("%d ",x1);
}

printf("\n");

for(i=1;i<=n+m;i++)
{
int x1,x2,c,q1=d1[l1],q2=d2[l2],q3=d3[l3];
if(q1>=q2&&q1>=q3) {x1=d1[l1];l1++;}
else
{
if(q2>=q1&&q2>=q3) {x1=d2[l2];l2++;}
else {x1=d3[l3];l3++;}
}

if(i%t==0) printf("%d ",x1+m*q);
}

//fclose(stdin);
//fclose(stdout);

return 0;
}

#include <bits/stdc++.h>
using namespace std;
priority_queue<int>q1;
queue<int>q2,q3;
int n,m,q,u,v,t;
int maxlen(int t){
int x1=-1,x2=-1,x3=-1;
if(!q1.empty())x1=q1.top()+t*q;
if(!q2.empty())x2=q2.front()+t*q;
if(!q3.empty())x3=q3.front()+t*q;
if(x1>=x2&&x1>=x3){q1.pop();return x1;}
else if(x2>=x1&&x2>=x3){q2.pop();return x2;}
else{q3.pop();return x3;}
}
int main(int argc,char** argv){
cin>>n>>m>>q>>u>>v>>t;
for(int i=1;i<=n;i++){int len;cin>>len;q1.push(len);}
for(int i=1;i<=m;i++){
long t1,t2,len=maxlen(i-1);
t1=len*u/v;t2=len-t1;
q2.push(t1-i*q);q3.push(t2-i*q);
if(i%t==0)cout<<len<<" ";

}cout<<endl;
for(int i=1;i<=m+n;i++){
int len=maxlen(m);
if(i%t==0)cout<<len<<" ";
}return 0;
}