题目描述

有 N 堆纸牌，编号分别为 1,2,…,N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。

移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。

现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。

输入格式

第一行共一个整数 N，表示纸牌堆数。  
第二行共 N 个整数 A1​,A2​,…,AN，表示每堆纸牌初始时的纸牌数。

输出格式

共一行，即所有堆均达到相等时的最少移动次数。

输入
4
9 8 17 6

输出 
3

说明/提示

对于 100% 的数据，1≤N≤100，1≤Ai​≤10000。

【题目来源】

NOIP 2002 提高组第一题

说一下本代码对样例的计算：

在输入完成后，sum的值为9+8+17+6=40，将sum(40)于n(4)相除，得到p(10)。然后通过for循环来计算。

第一堆纸牌数量为9，于10相差1，那么第二堆纸牌(8)给第一堆纸牌(9)一张牌，第一堆纸牌数量变为10，符合标准，第二堆纸牌数量变为7。（第一次循环）

第二堆纸牌数量为7，于10相差3，那么第三堆纸牌(17)给第二堆纸牌(7)三张牌，第二堆纸牌数量变为10，符合标准，第三堆纸牌数量变为14。（第二次循环）

第三堆纸牌数量为14，于10相差4，那么第三堆纸牌(14)给第四堆纸牌(6)四张牌，第三，四堆纸牌数量都变为10，符合标准。（第三次循环）

第四堆纸牌数量为10，符合标准，无事发生。（第四次循环）

#include <bits/stdc++.h>     //万能头文件
using namespace std;
int  n,sum,p,ans;            //定义牌堆总数n,纸牌总数sum,预估每一堆的总数p,最少移动次数ans
int  a[105];                 //每一牌堆的纸牌数量a数组,因为n最大值为100,所以开到105就可以
int main() {
    cin>>n;                  //输入n
    for(int i=1;i<=n;i++) {  //使用for循环来输入每一牌堆的纸牌数量
        cin>>a[i];           //输入每一牌堆的纸牌数量
        sum+=a[i];           //计算纸牌总数
    }
    p=sum/n;                 //因为题中说明纸牌总数是n的倍数,所以可以用除法求出预估每一堆的总数
    for(int i=1;i<=n;i++) {  //一堆一堆看
        if(a[i]!=p) {        //如果这一堆纸牌数量不等于预估每一堆的总数
        ans++;               //那么就需要移动,增加移动次数
        a[i+1]+=a[i]-p;      //如果a[i]小于p,那么a[i]-p为负数,a[i+1]加上就相当于把自己的纸牌给了a[i]。如果a[i]大于p,那么a[i]-p为正数,a[i+1]加上就相当于a[i]把多余的牌给了a[i+1]。可以在纸上写一下,更容易理解。
        }
    }
    cout<<ans;               //输出答案
    return 0;
}