蚯 蚓 好题

\[好题qwq\\ 想法是搞个堆,然后刚好满足,然后复杂度mlogn,就咕咕咕了\\ 因为0<p<1~~~~假设x_1\ge x_2且x_1x_2为非负整数,\lfloor px_1\rfloor+q=\lfloor px_1+q\rfloor\ge\lfloor px_2+pq\rfloor显然\\ 1秒后x_1被分成\lfloor px_1\rfloor+q和x_1-\lfloor px_1\rfloor+q\\ x_2被分成\lfloor p(x_2+q)\rfloor和x_2+q-\lfloor p(x_2+q)\rfloor\\ 不仅从集合取出的数是单调递减的,新产生的数值也是单调递减的\\ 所以建立三个队列。队列A保存初始的n个数,\\ 使用3个队列分别保存没被切过的蚯蚓,被切过的蚯蚓左段,和被切过的蚯蚓右段 \]

#include<cstdio>
#include<queue>
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
queue<int>a;queue<int>b;queue<int>c;
inline bool cmp(int x,int y){return x>y;}
int n,m,q,u,v,t;
inline int read(){
	char x;int num;
	while(x=getchar(),x<'0'||x>'9');num=x-'0';
	while(x=getchar(),x>='0'&&x<='9') num=(num<<3)+(num<<1),num+=x-'0'; return num;
}
int len[100100];
signed main(){
	n=read(),m=read(),q=read(),u=read(),v=read(),t=read();
	//n个蚯蚓 m秒内战况 每秒增加q p=u/v t输出参数
	for(int i=1;i<=n;i++)
	len[i] = read();
	sort(len+1,len+n+1,cmp);
	for(int i=1;i<=n;i++)
	a.push(len[i]);
	for(int i=1;i<=m;i++){
		int maxn = -0x7777777f,f=-1;
		if(!a.empty())if(a.front()>maxn)maxn=a.front(),f=1;
	    if(!b.empty())if(b.front()>maxn)maxn=b.front(),f=2;
	    if(!c.empty())if(c.front()>maxn)maxn=c.front(),f=3;
		if(f==1)a.pop();if(f==2)b.pop();if(f==3)c.pop();
		maxn+=(i-1)*q;int x=maxn*u/v;int y=maxn-x;
		if(!(i%t))cout<<maxn<<" ";b.push(x-i*q);c.push(y-i*q);
	}
	cout<<endl;
	int p=1;
		while(p){ 
		int maxn=-0x7777777f,f=-1;
		if(a.empty()&&b.empty()&&c.empty())break;
		if(!a.empty())if(a.front()>maxn)maxn=a.front(),f=1;
	    if(!b.empty())if(b.front()>maxn)maxn=b.front(),f=2;
	    if(!c.empty())if(c.front()>maxn)maxn=c.front(),f=3;
		if(f==1)a.pop();if(f==2)b.pop();if(f==3)c.pop();//如上
		if(p%t==0)
		  cout<<maxn+(m)*q<<" ";        
		p++;                             
	}
}
上一篇:stack容器


下一篇:cf669 div2 abcd