题解：P2827 [NOIP 2016 提高组] 蚯蚓

· · 题解

经 Jayne（老师，不敢@）和 @Lyzc0dr 的激烈讨论，得出来一种新做法。

首先我们明白一个不等式 x_1-\lfloor px_1 \rfloor \ge x_2 \lfloor px_2 \rfloor，具体证明过程请看 dbxxx的TJ。
根据这个不等式，我们可以考虑维护三个队列，而不必维护一个优先队列，因为三个队列始终保持满足单调性，无需使用优先队列（此处和其他 TJ 相同）。
然后根据此思路即可拿到所有 q = 0 的分，接下来为了解决 q > 0，通常方法都是计个 tag，加入队列时把两段都减掉一个 q，tag 加上一个 q。
考虑到一条在第 i 时刻加入的长度为 len 蚯蚓，如果在第 j 时刻被拿出来砍，因为它一共经历了 j - i - 1 次切割，一次切割长度加 q，所以总长度是 q \times (j - i - 1) + len。可以在常数时间内算出，不必打 tag 标记，只需多存个加入时间。

那么具体做法请看代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
const int maxn=2e5+10;
int n,m,Q,u,v,t,a[maxn];
queue<pii>q[4];//ABC三个队列
int get_max_len(int time){//取出最长的蚯蚓
    int x=-1e9,y=-1e9,z=-1e9;
    if(!q[1].empty())x=q[1].front().first+Q*(time-1-q[1].front().second);
    if(!q[2].empty())y=q[2].front().first+Q*(time-1-q[2].front().second);
    if(!q[3].empty())z=q[3].front().first+Q*(time-1-q[3].front().second);
    //分别取出三个队列队首
    int idx=1LL,tmp=0LL;//idx表示取出来哪一个队列的队首，tmp表示最大的队首
    if(x>=y && x>=z) tmp=x,idx=1;
    if(y>=x && y>=z) tmp=y,idx=2;
    if(z>=x && z>=y) tmp=z,idx=3;
    //更新tmp和idx
    q[idx].pop();//弹出
    return tmp;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>Q>>u>>v>>t;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);//正序排序（从小到大）
    for(int i=n;i>=1;i--) q[1].push({a[i],0});//倒序加入（从大到小）
    for(int i=1;i<=m;i++){
        int len=get_max_len(i),x,y;
        x=len*u/v,y=len-x;//分段
        if(i%t==0) cout<<len<<" ";//输出
        q[2].push({x,i}),q[3].push({y,i});//同其他TJ，加入B，C两个队列，始终保持单调
    }
    cout<<"\n";//换行
    for(int i=1;;i++){
        if(q[1].empty() && q[2].empty() && q[3].empty()) break;//三个队列都空了就停止
        int tmp=get_max_len(m+1);//继续获取最大的蚯蚓
        if(i%t==0) cout<<tmp<<" ";//输出
    }
    return 0;
}