欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Moving stones---------------------------思维(模拟+优先队列)

程序员文章站 2022-06-26 10:12:21
...

Moving stones---------------------------思维(模拟+优先队列)
Moving stones---------------------------思维(模拟+优先队列)
题意:
有n堆石头,现在选择d第i堆石头,需要从剩下来的n-1堆中各选出1个,放到第i堆。(没有的不取)
问最终是否能使得n堆石头的数量都一样

解析:
最容易看出来的就是如果n堆石头之和不能均分,那么肯定是输出NO
为了达到目的我们肯定是让小的+ 大的-
所以我们把这些数放到小根堆中
如何处理第i堆+(n-1) 其余堆-1 ??
可以O(1)的时间的复杂度做到。
我们只要用了计数器k,然后每次取出来的第一个都+n,等下次取出来的时候我们就减去k即可

如果我们-k得到的数正好等于平均数 那么输出Yes
如果我们-k<0 的话,只能输出No

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1000;
typedef long long ll;
typedef pair<ll,ll> PII;
priority_queue<ll,vector<ll>,greater<ll > > q;
ll a[N];
ll t,n;
inline int read() {
    int x=0;
    bool t=false;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}
int main()
{
	t=read();
	while(t--)
	{
		n=read();
		ll sum=0; 
		while(!q.empty()) q.pop();
		for(int i=1;i<=n;i++)
		{
			a[i]=read();
			sum+=a[i];
			q.push(a[i]);
		}
		if(sum%n!=0) cout<<"No"<<endl;
		else
		{
			ll avg = sum/n;
			ll k=0;
			int f=0;
			for(int i=1;i<=10000;i++)
			{
				if(q.top()-k==avg) {f=1;break;}
				if(q.top()-k<0)  {f=0;break;}
				ll tmp=q.top()+n;
				q.pop();
				k++;
				q.push(tmp);
				
			}
			if(f==1) cout<<"Yes"<<endl;
			else cout<<"No"<<endl;
		}
		
	}
 } 
相关标签: 思维