F - Stones in the Bucket

淡淡的烟草味﹌ 2022-01-30 08:13 177阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY2NzYxMQ_size_16_color_FFFFFF_t_70]  
**Output**

For each test case output one line containing one integer, indicating the minimum number of times needed to make all the buckets contain the same number of stones.

**Sample Input**

4  
3  
1 1 0  
4  
2 2 2 2  
3  
0 1 4  
1  
1000000000

**Sample Output**

2  
0  
3  
0

**Hint**

For the first sample test case, one can remove all the stones in the first two buckets.  
For the second sample test case, as all the buckets have already contained the same number of stones, no operation is needed.  
For the third sample test case, one can move 1 stone from the 3rd bucket to the 1st bucket and then remove 2 stones from the 3rd bucket.

题意：给你n堆石头，把他们分成每堆都一样的数目，可以移动也可以拿走，每次操作算一步。

思路：输入的时候统计一下总的和，如果就1堆，直接输出0。否则这n堆从小到大排序，在判断总和能不能整数这n堆，如果可以整除，就说明不需要移除，只需要移动，统计下平均数前面的数与平均数的差值就行了。如果不能整除，说明需要移除，就统计从平均数的后面与平均数的差值。

AC代码：

#include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int mmax=1e6+10;
    int a[mmax];
    int main()
    {
    	ll t;
    	cin>>t;
    	while(t--)
    	{
    		ll n;
    		cin>>n;
    		ll sum;
    		sum=0;
    		for(int i=1;i<=n;i++)
    		{
    			cin>>a[i];
    			sum+=a[i];
    		}
    		if(n==1)	
    			cout<<"0"<<endl;
    		else
    		{
    			sort(a+1,a+1+n);
    			if(sum/n==(double)sum/n)
    			{
    				ll ave=sum/n,ans1=0;
    				for(int i=1;i<=n;i++)
    				{
    					if(a[i]<=ave)
    					{
    						ans1+=(ave-a[i]);
    					}
    					else
    						break;
    				}
    				cout<<ans1<<endl;
    			}
    			else
    			{
    				ll ave=sum/n;
    				ll nun=0,k;
    				for(int i=1;i<=n;i++)
    				{
    					if(a[i]>=ave)
    					{
    						nun+=(a[i]-ave);
    					}
    				}
    				cout<<nun<<endl;
    			}
    		}
    			
    		
    	}
    	return 0;
     }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY2NzYxMQ_size_16_color_FFFFFF_t_70]: /images/20220130/2c3d1b8e4cc54001ab85e191337b432b.png