洛谷2827 [NOIP2016]蚯蚓

终于把这道一直85分懒得搞的题过了。

题意

最开始有 $n$ 只蚯蚓，每秒把最长的那条蚯蚓砍成两段，比例为 $p:(1-p)$ 。同时所有蚯蚓每秒增加 $q$ 的长度。

求每 $t$ 秒最长的蚯蚓长度，以及 $m$ 秒后排名为 $k\times t$ 的蚯蚓长度。

$n\le 10^5 \ , \ m\le 7\times 10^6$

题解

先对所有蚯蚓长度从大到小排序。将蚯蚓队列、$p$ 和 $(1-p)$ 分成三组来考虑，显然无论何时三组都是递减的。

所以可以开三个队列来维护，每秒最长的蚯蚓就是三个队列队首的最大值。

对于增加的长度，可以用 $Q$ 来表示所有蚯蚓的增加值，统计答案时加上即可。

注意队列中减去 $Q$ 后可能会出现负数，所以当队列为空时给队首赋 $-1$ 会锅。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

queue <ll> x,y,z;
ll n,m,q,u,v,t,cnt,now,s[100005],ans[7100005];

inline bool get_max()
{
    ll tx=x.empty() ? -1e9 : x.front();
    ll ty=y.empty() ? -1e9 : y.front();
    ll tz=z.empty() ? -1e9 : z.front();
    if (tx==-1e9 && ty==-1e9 && tz==-1e9) return 0;
    if (tx>=ty && tx>=tz) now=tx,x.pop();
    else if (ty>=tx && ty>=tz) now=ty,y.pop();
    else if (tz>=tx && tz>=ty) now=tz,z.pop();
    return 1;
}

signed main()
{
    n=read(); m=read(); q=read(); u=read(); v=read(); t=read();
    for (ll i=1;i<=n;i++) s[i]=read();
    sort(s+1,s+n+1);
    for (ll i=n;i;i--) x.emplace(s[i]);
    ll Q=0;
    for (ll i=1;i<=m;i++)
    {
        get_max();
        now+=Q; Q+=q;
        y.emplace(now*u/v-Q);
        z.emplace(now-now*u/v-Q);
        if (i%t==0) printf("%lld ",now);
    }
    puts("");
    while (get_max()) ans[++cnt]=now+Q;
    for (ll i=t;i<=cnt;i+=t) printf("%lld ",ans[i]);
    puts("");
    return 0;
}