NC16430 蚯蚓（队列）

题目链接

题意：
在m秒中有n只蚯蚓不断被分割，即每秒中长度最长的一只会被分割成两段，其余蚯蚓长度会增加q。求出每秒所分割的蚯蚓长度和最后各蚯蚓长度，按照格式要求输出。

题解：

暴力维护肯定会T，可以按照相对的思想，只对分割的蚯蚓操作，即分割蚯蚓长度少增加了q，大小关系不变，真正的长度等于队列元素加上“总位移”，“总位移”用一个变量记录就好。
由于m为7e6且纯用优先队列的话常数较大，考虑优化程序。
由于是按照长度从大到小分割，所分的两段可以分为两类且满足单调性，用两个队列O(m)就可以维护。
这样我们用三个队列表示未分割、所分割两类的蚯蚓长度，每次只需比较三个队首大小，就可求出最长蚯蚓。
总体上只需两遍mlogm的排序，按照题意操作即可。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int nx=7e6+5;
int a[nx],b[nx],c[nx],ans[nx];
int ha,hb,hc,na,nb,nc;
int m,t,q,u,v,f;
inline void in(int &x){
    x=0;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar());
    for(;ch>='0'&&ch<='9';ch=getchar())
        x=(x<<1)+(x<<3)+(ch&15);
}
inline void print(int x){
    if(x>9)print(x/10);
    putchar('0'+x%10);
}
int main(){
    in(na),in(m),in(q),in(u),in(v),in(t);
    for(int i=0;i<na;++i)in(a[i]);
    sort(a,a+na,greater<int>());
    for(int i=1;i<=m;++i){
        int x=ha<na?a[ha]:-0x3f3f3f3f,y=b[hb],z=c[hc],now;
        if(x>=y&&x>=z)now=a[ha++];
        else if(y>=x&&y>=z)now=b[hb++];
        else if(z>=x&&z>=y)now=c[hc++];
        now+=f;
        int n1=1ll*u*now/v,n2=now-n1;
        f+=q,n1-=f,n2-=f;
        b[nb++]=n1,c[nc++]=n2;
        if(i%t==0)print(now),putchar(' ');
    }putchar('\n');
    int p=0,en=na+m;
    for(int i=ha;i<na;++i)ans[++p]=a[i];
    for(int i=hb;i<nb;++i)ans[++p]=b[i];
    for(int i=hc;i<nc;++i)ans[++p]=c[i];
    sort(ans+1,ans+1+en,greater<int>());
    for(int i=1;i<=en;++i)
        if(i%t==0)print(ans[i]+f),putchar(' ');
}