NOIP2016 蚯蚓

题目:

   本题中,我们将用符号 表示对 向下取整,例如:
   蛐蛐国最近蚯蚓成灾了!隔壁跳蚤国的跳蚤也拿蚯蚓们没办法,蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。
   蛐蛐国里现在共有 只蚯蚓( 为正整数)。每只蚯蚓拥有长度,我们设第 只蚯蚓的长度为 (),并保证所有的长度都是非负整数(即:可能存在长度为 的蚯蚓)。
   每一秒,神刀手会在所有的蚯蚓中,准确地找到最长的那一只(如有多个则任选一个)将其切成两半。神刀手切开蚯蚓的位置由常数 (是满足 <<的有理数)决定,设这只蚯蚓长度为 ,神刀手会将其切成两只长度分别为 的蚯蚓。特殊地,如果这两个数的其中一个等于 ,则这个长度为 的蚯蚓也会被保留。此外,除了刚刚产生的两只新蚯蚓,其余蚯蚓的长度都会增加 (是一个非负整常数)。
   蛐蛐国王知道这样不是长久之计,因为蚯蚓不仅会越来越多,还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物,但是救兵还需要 秒才能到来……( 为非负整数)
   蛐蛐国王希望知道这 秒内的战况。具体来说,他希望知道:
   秒内,每一秒被切断的蚯蚓被切断前的长度(有 个数);
   秒后,所有蚯蚓的长度(有 个数)。
   蛐蛐国王当然知道怎么做啦!但是他想考考你……

思路:

   如果不考虑数据范围,比较简单的一个写法就是把所有的长度扔进堆,每次弹出最大值。蚯蚓的长度加 的操作可以在全局记一个变量,把不加的值减去 。但是这样做的复杂度是的。
   根据数据范围可以猜测复杂度大概是的。既然要的求出最大值,可以考虑要利用单调性。设为每次弹出的的数字,那么显然,分别是单调的。所以只要用三个队列维护最大值即可,每次取三个队列中的最大值就行了。

代码:

#include <bits/stdc++.h>
#define File(_) freopen(#_".in","r",stdin),freopen(#_".out","w",stdout)
#define rep(i,a,b) for(int i=(a),i##_END=(b);i<=i##_END;i++)
#define drep(i,a,b) for(int i=(a),i##_END=(b);i>=i##_END;i--)
typedef long long ll;
template<class T> bool tomin(T &a,T b){return a>b?a=b,1:0;}
template<class T> bool tomax(T &a,T b){return a<b?a=b,1:0;}
const int M=7e6+5,N=1e5+5;
template<int N,class T> struct Queue{
    int hed,tai;T q[N];
    Queue(){clear();}
    void clear(){hed=1;tai=0;}
    T front(){return q[hed];}
    T pop(){return q[hed++];}
    void push(T x){q[++tai]=x;}
    bool empty(){return hed>tai;} 
};
Queue<M,int> que[3];
int ans[M+N],q,u,v,tot,add=0;
void calc(){
    int max=-1;
    rep(i,0,2)
        if(!que[i].empty())
            tomax(max,que[i].front()+add);
    rep(i,0,2)
        if(!que[i].empty()&&que[i].front()+add==max){
            que[i].pop();
            break;
        }
    int x=(ll)max*u/v;
    add+=q;
    que[1].push(x-add);que[2].push(max-x-add);
    ans[++tot]=max;
}
int a[N];
int main(){
    //File(earthworm);
    int n,m,t;
    scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
    rep(i,1,n)scanf("%d",a+i);
    std::sort(a+1,a+1+n,std::greater<int>());
    rep(i,1,n)que[0].push(a[i]);
    rep(i,1,m)calc();
    for(int i=t;i<=m;i+=t)
        printf("%d%c",ans[i],i+t>m?'\n':' ');
    if(t>m)puts("");
    rep(i,1,n+m){
        int max=-1;
        rep(k,0,2)
            if(!que[k].empty())
                tomax(max,que[k].front()+add);
        rep(k,0,2)
            if(!que[k].empty()&&que[k].front()+add==max){
                ans[i]=que[k].pop()+add;
                break;
            }
    }
    for(int i=t;i<=n+m;i+=t)
        printf("%d%c",ans[i],i+t>n+m?'\n':' ');
    if(t>n+m)puts("");
    return 0;
}