当前位置:网站首页>P1031 divide cards equally (greedy)

P1031 divide cards equally (greedy)

2021-08-10 08:04:05 wx6110fa547fd20

P1031 Divide the cards equally ( greedy )

  Subject portal

The question :N Stack cards to find the minimum number of moves so that the number of cards in each stack is the same ( The optimal solution is guaranteed and can only move adjacent )

Ideas : According to greedy thought : Obviously, two adjacent stacks of cards can move at most once , We calculate the difference between each pile of cards and the average , obtain ( Number of difference or more ) So let's start with the first pile of cards , If the difference a[1] Not for 0, It means that these two adjacent piles need to be moved once , The difference of the first pile can only be given by the second pile , So update the difference of the second pile a[2]+=a[1], Then the first pile is finished, regardless of , At this time, the second pile can be regarded as the current first pile , Keep pushing , You can calculate the result .

#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://chowdera.com/2021/08/20210810080205535t.html

随机推荐