Moving stones---------------------------思维(模拟+优先队列)
程序员文章站
2022-06-26 10:12:21
...
题意:
有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;
}
}
}