题解：P2827 [NOIP2016 提高组] 蚯蚓

· · 题解

想了好久明白了。

首先，我们看到了一个险恶的数据 m=7\times10^6，一看就是来卡 \mathcal O(m\log m) 的。

怎么办？

考虑用普通的队列。

首先把初始 a_i 从大到小排序，然后考虑怎么利用数据单调性。

我们发现，\lfloor px\rfloor 是单调的。

而 x-\lfloor px \rfloor 在整点上是单调的。

这个东西是我在 Desmos 里画了一次，然后就出来了，具体证明看点赞最多的那篇题解的。

那这题就解决了一半。我们把切开的两只蚯蚓分开计算，都是单调的，然后直接在 3 个队列里找最长的蚯蚓切割即可。

但是，相信有部分读者只会处理 q=0。

我们发现，我们可给新加入的元素都减去一个偏移值。

设第 i 时间为 t。为了方便，我们将其设置为 t-1，一次生长长度加 q，那么 t-1 次生长就是 (t-1)\times q。挺好理解的。

当然，取出时要复原长度，加上 (i-1)\times t，这时就可以把一开始减去的抵消，处理完成。

没什么可以讲的了，更多内容请看点赞数最高题解。

#include<bits/stdc++.h>
//#include<bits/extc++.h>
using namespace std;
//using namespace __gnu_pbds;
//#define arr array<int,3>
//#define int long long
//#define double long double
//#define map unordered_map
//#pragma GCC optimize(2,3,"Ofast","inline")
const int N=1e5+10,M=1010,INF=1e9+7,MOD=998244353;
const double PI=3.1415926,EPS=0.00001;
int n,m,q,u,v,t,a[N],len,wormc[2];
long double p;
queue<int>worm[3];
pair<int,int>cut;
void getworm(int i){
    cut=max({
        pair<int,int>{worm[0].empty()?-INF:worm[0].front(),0},
        pair<int,int>{worm[1].empty()?-INF:worm[1].front(),1},
        pair<int,int>{worm[2].empty()?-INF:worm[2].front(),2}
    });
    len=cut.first+q*(i-1);
    worm[cut.second].pop();
}
signed main(){
    cin>>n>>m>>q>>u>>v>>t;
    p=u*1.00;p/=v;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1,greater<int>());
    for(int i=1;i<=n;i++)worm[0].push(a[i]);
    for(int i=1;i<=m;i++){
        getworm(i);
        wormc[0]=p*len;
        wormc[1]=len-wormc[0];
        worm[1].push(wormc[0]-q*i);
        worm[2].push(wormc[1]-q*i);
        if(!(i%t))cout<<len<<" ";
    }   
    cout<<"\n";
    for(int i=1;i<=n+m;i++){
        getworm(m+1);
        if(!(i%t))cout<<len<<" ";
    }
    return 0;
}
//note: