P2827 蚯蚓

题目链接
思路
代码

题目链接

思路

如果是\(q=0\)的话，相当于维护一个集合，支持查询最大值，删除最大值，添加新值,用\(set\)即可实现

如果是\(q>0\)的话,我们可以把用刀切看成是，把最大值\(x\),分成\(\left\lfloor px\right\rfloor-q\)和\(x-\left\lfloor px\right\rfloor-q\)，然后给把整个集合都加上\(q\),所以我们可以维护一个变量\(ans\)表示整个集合的偏移量,集合中的数加上\(ans\)就是真实值开始我们让\(ans=0\)

对于每一秒:

1.取出集合中的最大值x,令\(x=x+ans\)

2.把\(\left\lfloor px\right\rfloor-q\)和\(x-\left\lfloor px\right\rfloor-q\)插入集合

3.令\(ans+=q\)

用三个队列\(q1,q2,q3\)共同组成要维护的集合,\(q1\)保存初始的\(n\)个数,从大到小排序。\(q2\)存储 \(\left\lfloor px\right\rfloor\)

,\(q3\)存储 \(x-\left\lfloor px\right\rfloor\) ，每个时刻最大的数就是\(q1,q2,q3\)队首之一。

我们来证明一下集合中取出的数是单调递减的，而且新生成的数也是单调递减的

因为\(p,q\)是常数,\(0<p<1\)而且\(p\)是非负整数,设\(x_1,x_2\)是非负整数

当\(x_1>=x_2\)时，\(\left\lfloor px_1\right\rfloor+q=\left\lfloor px_1+pq\right\rfloor>=\left\lfloor px_2+pq\right\rfloor=\left\lfloor p(x_2+q)\right\rfloor\)

又因为\(x_1>x_2>=p(x_1-x_2)\)

所以\(x_1-px_1>=x_2-px_2>=x_2-p(x_2+q)\)

所以\(x_1-\left\lfloor px_1\right\rfloor+q=\left\lfloor x_1-px_1\right\rfloor+q>=\left\lfloor x_2-p(x_2+q)\right\rfloor+q>=x_2+q-\left\lfloor p(x_2+q)\right\rfloor\)

即：

若\(x_1\)在\(x_2\)之前被取出集合，那么一秒之后\(x_1\)被分成\(\left\lfloor px\right\rfloor-q\)和\(x-\left\lfloor px\right\rfloor-q\)分别不小于x_2+q分成的两个数

\(\left\lfloor x_2-p(x_2+q)\right\rfloor+q\)和\(x_2+q-\left\lfloor p(x_2+q)\right\rfloor\)

证毕（写死我了）

代码

#include<bits/stdc++.h>

#include<queue>

#define int long long int

#define p u/v

using namespace std;

int n,m,q,u,v,t,a[7004015];

int cmp(int x,int y) {

	return x>y;

}

queue<int>q1,q2,q3;

int calc(int t) {

	int x=0,a=0,b=0,c=0;

	if(!q1.empty()) a=q1.front()+t*q;

	if(!q2.empty()) b=q2.front()+t*q;

	if(!q3.empty()) c=q3.front()+t*q;

	x=max(a,max(b,c));

	if(x==a) q1.pop();

	else if(x==b) q2.pop();

	else if(x==c) q3.pop();

	return x;

}

signed main() {

//	freopen(".in","r",stdin);

//	freopen(".out","w",stdout);

	cin>>n>>m>>q>>u>>v>>t;

	//n只蚯蚓 m秒  	p=u/v 	t是输出参数

	for(int i=1; i<=n; ++i) cin>>a[i];

	sort(a+1,a+1+n,cmp);

	for(int i=1; i<=n; ++i) q1.push(a[i]);

	for(int i=1; i<=m; ++i) {

		int x=calc(i-1);

		if(!(i%t)) cout<<x<<' ';

		int now1=x*p;//注意这里要先乘后除

		int now2=x-now1;

		q2.push(now1-i*q);

		q3.push(now2-i*q);

	}

	cout<<endl;

	for(int i=1; i<=(n+m); ++i) {

		int x=calc(m);

		if(!(i%t)) cout<<x<<' ';

	}

	return 0;

}

巴特西

P2827 蚯蚓

题目链接

思路

代码

最新文章

热门文章