题解：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

，这时就可以把一开始减去的抵消，处理完成。

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

CPP

#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:

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

文章操作

相关推荐

评论

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