当前位置:网站首页>P1031 均分纸牌 (贪心)

P1031 均分纸牌 (贪心)

2021-08-10 08:02:35 wx6110fa547fd20

P1031 均分纸牌 (贪心)

 题目传送门

题意:N堆纸牌求最小移动次数使每堆纸牌数相同(保证优解且只能相邻移动)

思路:根据贪心思想:显然相邻两堆纸牌最多移动一次,我们算出每堆纸牌与平均值的差值,得到(差或多的个数)所以我们从第一堆纸牌开始,如果差值a[1]不为0,说明这相邻两堆需要移动一次,第一堆的差值只能由第二堆给予,所以更新第二堆的差值a[2]+=a[1],然后第一堆完成不管,此时的第二堆可以看作为当前第一堆,一直递推下去,即可计算出结果。

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,sum=0;
	cin>>n;
	int a[n+1],ans=0;
	for(int i=1;i<=n;i++)
		cin>>a[i],sum+=a[i];;
	sum/=n;
	for(int i=1;i<=n;i++)
		a[i]-=sum;
	for(int i=1;i<=n;i++)
		if(a[i]) a[i+1]+=a[i],ans++;
	cout<<ans<<endl;
	return 0;
}

      
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.

版权声明
本文为[wx6110fa547fd20]所创,转载请带上原文链接,感谢
https://blog.51cto.com/u_15326986/3328301

随机推荐