【GESP】C++五级练习题 luogu-P1031 [NOIP 2002 提高组] 均分纸牌
GESP C++ 五级练习题，贪心思想思想考点。题目难度⭐⭐★☆☆，适合五级入门和四级练习，洛谷难度等级普及-。
luogu-P1031 [NOIP 2002 提高组] 均分纸牌
题目要求
题目描述
有 $N$ 堆纸牌，编号分别为 $1,2,\ldots,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$ 个整数 $A_1,A_2,\ldots,A_N$，表示每堆纸牌初始时的纸牌数。
输出格式
共一行，即所有堆均达到相等时的最少移动次数。 第二行共 $N$ 个整数 $A_1,A_2,\ldots,A_N$，表示每堆纸牌初始时的纸牌数。
输出格式
共一行，即所有堆均达到相等时的最少移动次数。
输入输出样例 #1
输入 #1
1
2
4
9 8 17 6
输出 #1
1
3
说明/提示
对于 $100\%$ 的数据，$1 \le N \le 100$，$1 \le A_i \le 10000$。
【题目来源】
NOIP 2002 提高组第一题
题目分析
这道题目是一个典型的贪心算法问题。我们的目标是用最少的移动次数使每堆纸牌数相等。
1. 问题转化与核心思路
题目要求每堆纸牌最终数量相等。首先，我们可以计算出所有纸牌的总数 sum，然后除以堆数 N，得到每一堆最终应该拥有的纸牌数 target = sum / N。
接下来，我们需要考虑如何移动。为了使移动次数最少，我们可以采用从左往右扫描的策略：
- 考虑第 $1$ 堆：
- 如果第 $1$ 堆的纸牌数 $A_1$ 已经是
target，则不需要移动，继续看下一堆。 - 如果 $A_1 \neq target$，为了让第 $1$ 堆达到
target，它只能与第 $2$ 堆进行交换（因为第 $1$ 堆左边没有堆）。- 如果 $A_1 > target$（多了），需要把多出的 $A_1 - target$ 张牌移给第 $2$ 堆。
- 如果 $A_1 < target$（少了），需要从第 $2$ 堆移过来 $target - A_1$ 张牌（相当于把负数的差额移给第 $2$ 堆）。
- 无论哪种情况，都需要进行一次移动操作（题目定义“可以在任一堆上取若干张纸牌，然后移动”算一次）。
- 移动后，第 $1$ 堆达标，第 $2$ 堆的数量变成了 $A_2 + (A_1 - target)$。
- 考虑第 $2$ 堆：
- 此时第 $1$ 堆已经处理完毕，不再变动。
- 如果现在的 $A_2$ 不等于
target，它只能与第 $3$ 堆交互（因为不能破坏已经平衡的第 $1$ 堆）。 - 将差额转嫁给第 $3$ 堆，步数 $+1$。
- 以此类推，对于第 $i$ 堆（$1 \le i < N$）：
- 如果 $A_i \neq target$，步数 $+1$。
- 将 $A_i$ 与
target的差值累加到 $A_{i+1}$ 上：$A_{i+1} = A_{i+1} + (A_i - target)$。 - $A_i$ 变为
target（实际上代码中可以不更新 $A_i$，只更新 $A_{i+1}$ 即可）。
2. 为什么这样做是最优的？
- 当我们在处理第 $i$ 堆时，假设前 $i-1$ 堆都已经达到了
target。 - 如果第 $i$ 堆不达标，为了不破坏前 $i-1$ 堆的平衡，第 $i$ 堆只能与第 $i+1$ 堆进行交换。
- 这种依赖关系是单向传递的，每一次必要的交换都解决了当前堆的问题，并将“包袱”甩给了下一堆，直到最后一堆。
- 由于最后一堆 $A_N$ 在前 $N-1$ 堆都达标后，必然也会自动达标（因为总数守恒），所以不需要单独处理第 $N$ 堆。
3. 算法步骤
- 读取 $N$ 和每一堆的初始数量，计算总数
sum。 - 计算平均值
target = sum / N。 - 初始化步数
step = 0。 - 遍历 $i$ 从 $1$ 到 $N-1$，如果 $A[i] \neq target$：
step加 $1$。- 将差额移给下一堆：$A[i+1] += A[i] - target$。
- 输出
step。
这种贪心策略保证了每一步移动都是为了满足当前最左侧不平衡堆的刚需，且不产生多余的操作，因此移动次数最少。
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
int a[105]; // 定义数组存放每堆纸牌数，大小略大于100
int main() {
int N;
std::cin >> N; // 输入纸牌堆数 N
int sum = 0; // 用于存储纸牌总数
for (int i = 1; i <= N; i++) {
std::cin >> a[i]; // 输入每堆纸牌的初始数量
sum += a[i]; // 累加总数
}
int target = sum / N; // 计算平均每堆纸牌应有的数量
int step = 0; // 记录移动次数
// 从左向右遍历每一堆纸牌 (贪心算法)
// 思想：如果当前堆不等于平均值，只能和右边相邻的堆进行交换（因为左边已经平衡了）
for (int i = 1; i <= N; i++) {
if (i == 1) {
// 第一堆只能移向第二堆，或者从第二堆移入
if (a[1] != target) {
step++; // 需要移动一次
a[2] +=
a[1] -
target; // 将差额加到下一堆（多退少补，只是数值上的转移）
a[1] = target; // 当前堆达到平均值
}
} else {
// 处理后续的堆
if (a[i] != target) {
step++; // 需要移动一次
a[i + 1] += a[i] - target; // 将当前堆的盈亏转移给下一堆
a[i] = target; // 当前堆达到平均值
}
}
}
std::cout << step << std::endl; // 输出最少移动次数
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
