SCU-1005: Move cards

约定不等于承诺〃 2022-08-20 07:17 43阅读 0赞

# 1005: Move cards #

<table> 
 <tbody> 
  <tr> 
   <td><a href="http://acm.scu.edu.cn/soj/submit_form.action?id=1005" rel="nofollow">Submit your solution</a> &nbsp;&nbsp;&nbsp; <a href="http://acm.scu.edu.cn/soj/discuss/topics.action?id=1005" rel="nofollow"> Discuss this problem</a> &nbsp;&nbsp;&nbsp; <a href="http://acm.scu.edu.cn/soj/problem_best_solutions.action?id=1005" rel="nofollow"> Best solutions</a></td> 
  </tr> 
  <tr> 
   <td> <h2>The Problem</h2> <p>There are N piles of cards, and these piles are numbered as 1,2,...,N respectively. Each pile has some cards, while the total of all cards must be a multiple of N. The player can take some cards from one pile and then put them on another pile as one step.</p> <p>The follow is the rules: the cards on the pile numbered 1 can only be moved to the pile 2; the cards on the pile N can only be moved to the pile N-1; the cards on other piles, numbered from 2 to N-1, can be moved to either their left pile or right one.</p> <p>Now the player should move these cards to make the card numbers of each pile equal by minimum steps.</p> <p>For example: there are 4 piles, and the card numbers of each pile are 9 8 17 6 respectively. So it needs 3 steps to achieve the goal at least.</p> <h2>The Input</h2> <p>The input file consists of one or more test cases. The first line of input is the number of cases. Each case contains 2 lines: the first line of each case contains the only number N indicating the number of piles, and the second line contains a group of integers separated by space, indicating the card numbers of each pile respectively.</p> <h2>The Output</h2> <p>The minimum steps to make all piles' card numbers equal.</p> <p>&nbsp;</p> <h2>Sample input</h2> <pre><code>1
4
9 8 17 6</code></pre> <h2>Sample output</h2> <pre><code>3</code></pre> <p>&nbsp;</p> <p>解题思路：</p> <p>要将他们变成相同的数我们就要做到，将他们变成平均数。所以计算出他们的平均数然后，依次和平均数进行比较，并且从后边的数上加上或减去，等于平均数不用记录步数。</p> <p>&nbsp;</p> <pre><code>#include&lt;stdio.h&gt;
#include&lt;string.h&gt;
#include&lt;algorithm&gt;
using namespace std;
int map[1000000],n;
 
int main()
{
	int T;
	scanf("%d",&amp;T);
	while(T--)
	{
		scanf("%d",&amp;n);
		int i,j;
		int ss=0;
		for(i=0;i&lt;n;i++)
		{
			scanf("%d",&amp;map[i]);
			ss+=map[i];
		}
		ss=ss/n;
		int ans=0;
		for(i=0;i&lt;n-1;i++)
		{
			if(map[i]&gt;ss)
			{
				map[i+1]+=map[i]-ss;
				map[i]=ss;
				ans++;
			}
			if(map[i]&lt;ss)
			{
				map[i+1]-=ss-map[i];
				map[i]=ss;
				ans++;
			}
		}
		printf("%d\n",ans);
	}	
	return 0;
}</code></pre> &nbsp; <p>&nbsp;</p> </td> 
  </tr> 
 </tbody> 
</table>