记录编号	431681	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]蚯蚓	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	1.882 s
提交时间	2017-08-01 15:54:02	内存使用	61.73 MiB

#include<bits/stdc++.h>
/*证明不知道严不严谨，我忽略了向下取整这一条件，不过这一条件应该是不影响结果的*/
/*开三个队列，一个记录最开始的，另外两个分别记录p和1-p，我们可以证明两个队列都是具有单调性的
假设第一个队列里有ab，a>b，那么我们切开a,其他两个队列里加入[a*p],a-[a*p],b变成了b+q，由于
2.3队列是等价的，所以我们考虑一二队列,假设b+q<[a*p],那么切开[a*p],再加入,无论在第二个还是第三个
队列他都满足递减，反过来如果b+q>[a*p],那么我们在2队列中加入[（b+q）*p],[a*p]变成了[a*p]+q
b<a,p<1,所以依然递减,这时候再切[a*p]+q,变成了（[a*p]+q）*p,[（b+q）*p]变成了[（b+q）*p]+q
pq抵消掉，那么变成了比较b*p+q和a*p*p,因为先切（b+q)得到了（b+q)*p，所以(b+q)>a*p,又因为p<1
所以b*p+q>a*p*p,即（[a*p]+q）*p<[（b+q）*p]+q，那么队列依旧满足单调递减*/
using namespace std;
int n,m,q,u,v,t,val,a[100005],b[8000005],c[8000005];
int a_head=1,a_tail,b_head=1,b_tail,c_head=1,c_tail;
int getmax()
{
	int ma=-0x7fffffff,x=0;
	if(a_head<=a_tail)
	{
		if(ma<a[a_head])
		{
			x=1;
			ma=a[a_head];
		}
	}
	if(b_head<=b_tail)
	{
		if(ma<b[b_head])
		{
			x=2;
			ma=b[b_head];
		}
	}
	if(c_head<=c_tail)
	{
		if(ma<c[c_head])
		{
			x=3;
			ma=c[c_head];
		}
	}
	if(x==1)
	a_head++;
	if(x==2)
	b_head++;
	if(x==3)
	c_head++;
	return ma;
}
bool cmp(int x,int y)
{
	return x>y;
}
int main()
{
	freopen("earthworm.in","r",stdin);
	freopen("earthworm.out","w",stdout);
//	freopen("1.txt","r",stdin);
	scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
	double p=(double)u/v;//存在一个优先级的问题 ，如果不给uv加括号，那么就是double/int可以得到double,但如果加上，就是int/int,
	//自动向下取整后才转换为double, 0.333会被当做0处理 
	for(int i=1;i<=n;i++)
	scanf("%d",&a[++a_tail]);
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=m;i++)
	{
		int x=getmax();
		x+=val;
		if(i%t==0)
		cout<<x<<" ";
		int tem1=x*p;//cout<<tem1<<" ";
		b[++b_tail]=tem1-q-val;//一定要-val啊现在他是真实值，-val才能进队列 
		c[++c_tail]=x-tem1-q-val;
		val+=q;
	}
	cout<<endl;
	for(int i=1;i<=n+m;i++)
	{
		int x=getmax();
		if(i%t==0)
		printf("%d",x+val);
	}
	return 0;
}