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

标记，只需多存个加入时间。

那么具体做法请看代码：

CPP

#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;
}

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

文章操作

相关推荐

评论

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