[noip2016]蚯蚓 题解

嗯，这道题，有一种蜜汁优先队列既视感，既然，就用优先队列吧，但是，这样肯定超时，过不了呀。

考虑优化一下，其实每次的长度增长都是一样的，我们可以最后再考虑这一增量。这样，长度肯定是单减的，我们开三个队列维护一下就好了。一个存初始的，剩下两个存砍断的。每次的增量差不多就是入队顺序，注意一下细节就好了。

貌似bzoj过不了，不知道为何，但是官方数据和洛谷都是可以过的，求大神指正。

#include<bits/stdc++.h>
#define N 8010000
using namespace std;
int n,m,q,u,v,t,tmp,mx,id,x,y;
int Q[3][N+5],l[3],r[3];
inline char nc()
{
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    int x=0,b=1;
    char c=nc();
    for(;!(c<='9'&&c>='0');c=nc())if(c=='-')b=-1;
    for(;c<='9'&&c>='0';c=nc())x=x*10+c-'0';
    return x*b;
}
inline bool cmp(const int &A,const int &B)
{
    return A>B;
}
int main()
{
    freopen("in.txt","r",stdin);
    n=read(),m=read(),q=read(),u=read(),v=read(),t=read();
    memset(Q,63,sizeof(Q));
    for(int i=1;i<=n;i++)Q[0][i]=read();
    sort(Q[0]+1,Q[0]+n+1,cmp);
    l[0]=1,r[0]=n,l[1]=l[2]=1,r[1]=r[2]=0;
    for(int i=1;i<=m;i++)
    {
        mx=-1000000000;
        for(int j=0;j<3;j++)if(Q[j][l[j]]>mx&&l[j]<=r[j])mx=Q[j][l[j]],id=j;
        mx+=tmp;        
        x=(int)(u*1.0/v*mx);y=mx-x;
        tmp+=q;x-=tmp,y-=tmp;
        if(i%t==0)printf("%d ",mx);
        Q[1][++r[1]]=x,Q[2][++r[2]]=y;
        l[id]++;
    }
    putchar('\n');
    for(int i=1;i<=n+m;i++)
    {
        mx=-1000000000;
        for(int j=0;j<3;j++)if(Q[j][l[j]]>mx&&l[j]<=r[j])mx=Q[j][l[j]],id=j;
        l[id]++;
        if(i%t==0)printf("%d ",mx+tmp);
    }
    return 0;
}