贪心算法实战解析：GESP五级C++均分纸牌问题（洛谷P1031）

这道题是GESP 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 个整数，表示每堆纸牌初始时的纸牌数。

输出格式
一行，即最少移动次数。

输入样例 #1

4
9 8 17 6

输出样例 #1

3

数据范围与提示
对于 100% 的数据，1≤N≤100，1≤每堆纸牌数≤10000。
题目来源：NOIP 2002 提高组第一题

贪心算法分析与思路

这道题是一个典型的贪心算法应用。核心目标是使用最少的移动次数使得所有堆的纸牌数量相等。

1. 问题转化

首先，计算所有纸牌的总数 sum，那么每一堆最终的目标纸牌数 target = sum / N。
问题的关键转化为：如何通过最少的相邻移动，使每个位置的数值都等于 target。

2. 贪心策略

我们可以采用从左到右的顺序依次处理每一堆纸牌。这个策略是解决此类平衡问题的经典贪心算法思想。

核心逻辑如下：

1. 从第一堆开始检查。假设当前检查第 i 堆。
2. 如果第 i 堆的纸牌数 a[i] 不等于 target，那么必须进行一次移动。
   • 若 a[i] > target，则将多余的 (a[i] - target) 张牌移给第 i+1 堆。
   • 若 a[i] < target，则视为从第 i+1 堆“借” (target - a[i]) 张牌过来（在代码中表现为第 i+1 堆减少相应数量）。
3. 移动后，第 i 堆的数量变为 target。接下来，我们不再回头处理第 i 堆，而是继续处理第 i+1 堆。
4. 重复此过程，直到处理完第 N-1 堆。由于总数守恒，最后一堆（第 N 堆）在处理完前 N-1 堆后会自动等于 target，无需额外操作。

为什么这样是最优解？
因为当我们处理第 i 堆时，其左侧的所有堆都已经调整完毕（等于 target）。为了不破坏左侧已经达成的平衡，第 i 堆只能与右侧相邻的第 i+1 堆进行“交易”。每一次移动都是解决当前堆不平衡的唯一且必需的操作，因此总移动次数最少。

3. 算法步骤与代码实现

基于以上分析，我们可以简化操作：不需要真正更新 a[i] 为 target，只需要一个变量记录当前堆累积的“盈亏差额”，并将其传递给下一堆即可。

#include <iostream>
#include <cmath> // 使用abs函数计算绝对值
using namespace std;

int main() {
    int N;
    cin >> N;
    int cards[105]; // 存储每堆牌数
    int sum = 0;

    // 读入数据并计算总和
    for (int i = 0; i < N; ++i) {
        cin >> cards[i];
        sum += cards[i];
    }

    int target = sum / N; // 计算目标平均值
    int balance = 0;      // 记录当前累积的差额
    int steps = 0;        // 记录移动次数

    // 贪心算法核心：从左到右传递差额
    for (int i = 0; i < N; ++i) {
        balance += cards[i] - target; // 计算当前堆与目标的差值并加入累积差额
        if (balance != 0) { // 如果累积差额不为0，说明需要进行一次移动来平衡
            steps++;
        }
        // balance的值会自动传递给下一轮循环（即下一堆）
    }

    cout << steps << endl;
    return 0;
}

代码说明：

• balance 变量是关键。它记录了从第一堆到当前堆，所有堆的纸牌总数与“应有总数”（i * target）之间的累计差值。
• 当 balance != 0 时，意味着这些累计的“盈亏”还没有被一次移动完全消化，必须发生一次纸牌传递，因此步数 steps 加一。
• 这种方法在思路上更清晰，代码也更简洁，是解决此类问题的标准写法，深刻体现了贪心算法的精髓。

总结

本题通过“均分纸牌”这一具体模型，生动地展示了贪心算法的应用场景与证明思路。掌握这种“从左到右，传递差额”的贪心策略，对于解决NOIP/CSP乃至GESP考试中类似的平衡、分配问题大有裨益。扎实的算法基础是进行高效、稳定系统编程的基石。