目录

题目描述

输入格式

输出格式

说明/提示

个人思路

代码（C++）

---

题目描述

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

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

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

例如 N=4 时，4 堆纸牌数分别为 9,8,17,6。

移动 3 次可达到目的：

• 从第三堆取 4 张牌放到第四堆，此时每堆纸牌数分别为 9,8,13,10。
• 从第三堆取 3 张牌放到第二堆，此时每堆纸牌数分别为 9,11,10,10。
• 从第二堆取 1 张牌放到第一堆，此时每堆纸牌数分别为 10,10,10,10。

输入格式

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

输出格式

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

说明/提示

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

个人思路

这题是一道典型的贪心算法。

首先，由于最终所有堆均达到相等，所以最后的牌数肯定是纸牌总数的平均数（其中纸牌总数可以在输入时进行统计，少写一个for循环）

sum = sum / n;

之后移动次数就只与平均数有关系了，大可把a[ i ]转换为其与sum的差：

for ( int i = 1; i <= n; i++ )
{
    a[ i ] = a[ i ] - sum;
}

由于贪心，局部最优解导致全局最优解，所以我们只需要让每堆牌都一次移好就好啦！

再解释一下吧：

如果a[ 1 ] ~ a[ k - 1 ] 都等于零，而a[ k ] ≠ 0 ，那么a[ k + 1 ] = a[ k + 1 ] + a[ k ]。

注意：由于我们每堆牌都要一次移好，所以a[ k ]移好之后就不用管了，所以a[ k ] = 0可有可无。

那刚才那个式子从何而来呢？

a[ k + 1 ] = a[ k + 1 ] + a[ k ];

1. a[ k ] ＞0：那么就要向第k + 1堆移动a[ k ]张牌（毕竟第k - 1堆已经好了），等式成立。
2. a[ k ] ＜0：那么第k + 1堆就要向第k堆移动 - a[ k ]张牌（毕竟第k - 1堆已经好了），即：

   a[ k + 1 ] = a[ k + 1 ] - ( -a[ k ] );

        等式仍然成立。

所以移动牌的程序就可以这样写：

int ans = 0;        //记录移动次数

for ( int i = 1; i <= n; i++ )
{
    if( a[ i ] == 0 )        //判断是否需要移动牌
        continue；            //避免在不用移牌时ans++
    a[ i + 1 ] = a[ i + 1 ] + a[ i ];        //移牌
    ans++;        //移动次数加一
}

也可以这样写：

int ans = 0;        //记录移动次数

for ( int i = 1; i <= n - 1; i++ )
{
    if( a[ i ] ！= 0 )        //判断是否需要移动牌
        ans++;            //增加移动次数
    a[ i + 1 ] = a[ i + 1 ] + a[ i ];        //移牌，此时a[ i ] == 0也没有关系
}

这样基本就能AC了！只要别手滑打错代码就行。我就把a[ i ] == 0打成i == 0了，结果才20……

但还是会有细心的小伙伴会问（比如我）：为什么代码1中 i 可以等于n呢？a[ n + 1 ]不会越界吗？

其实这些担心纯属多余，a[ n - 1 ]移动完成后，a[ n ]一定等于0，不然怎么做到平均数为sum呢？所以第7行根本不会执行。但代码2中就不行了，所以i <= n - 1。

代码（C++）

#include <bits/stdc++.h>

using namespace std;

int n, a[ 101 ], sum, ans = 0;

int main() {
    scanf("%d", &n);
    for ( int i = 1; i <= n; i++ )
    {
         scanf("%d", &a[ i ]);
         sum = sum + a[ i ];
    }
    sum = sum / n;

    for ( int i = 1; i <= n; i++ )
    {
        a[ i ] = a[ i ] - sum;
    }

    for ( int i = 1; i <= n; i++ )
    {
        if ( a[ i ] == 0 )
            continue;
        a[ i + 1 ] = a[ i + 1 ] + a[ i ];
        ans++;
    }

    printf("%d", ans);

    return 0;
}

完结撒花！