[NOIP2002 提高组] 均分纸牌

题目描述

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

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

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

例如N=4，4堆纸牌数分别为：

①9②8③17④6

移动3次可达到目的：

从 ③ 取4张牌放到 ④ （9,8,13,10）-> 从 ③ 取33张牌放到 ②（9,11,10,10）-> 从 ② 取11张牌放到①（10,10,10,10）。

输入格式

两行

第一行为：NN（NN 堆纸牌，1≤N≤100）

第二行为：A1,A2,…,An（N堆纸牌，每堆纸牌初始数，1≤Ai≤100001≤Ai​≤10000）

输出格式

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

输入数据 1

4
9 8 17 6

输出数据 1

3

根据题目描述，我们需要将所有堆的纸牌数量调整为相等，并且要求移动次数最少。通过分析可以发现，每个非目标值的堆都需要至少一次移动来调整其数量，因此最少移动次数等于需要调整的堆的数量减一（当相邻堆都需要调整时，可以合并移动）。

以下是解决该问题的 C++ 代码：
 

#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> cards(n);
int sum = 0;
for (int i = 0; i < n; i++) {
cin >> cards[i];
sum += cards[i];
}
int avg = sum / n;
for (int i = 0; i < n; i++) {
cards[i] -= avg;
}
vector<int> prefix(n);
prefix[0] = cards[0];
for (int i = 1; i < n; i++) {
prefix[i] = prefix[i-1] + cards[i];
}
int count = 0;
for (int i = 0; i < n; i++) {
if (prefix[i] != 0) {
count++;
}
}
cout << count << endl;
return 0;
}

代码说明：

该算法的时间复杂度为 O (n)，能够高效处理题目给定的数据范围。

让我们通过逐步拆解问题和代码逻辑，深入理解如何通过前缀和数组的非零元素数量确定最少移动次数。

一、问题本质分析

二、代码逻辑详解

1. 输入处理与平均值计算

int n;
cin >> n;
vector<int> cards(n);
int sum = 0;
for (int i = 0; i < n; i++) {
cin >> cards[i];
sum += cards[i];
}
int avg = sum / n;

• 输入处理：读取堆数n和每堆的初始纸牌数。
• 平均值计算：总和sum除以堆数n得到目标值avg。若纸牌总数不是n的倍数，题目保证输入合法，因此无需处理。

2. 调整数组（差值数组）

for (int i = 0; i < n; i++) {
cards[i] -= avg;
}

• 差值数组：将每堆的纸牌数转换为与平均值的差值。例如，若某堆初始有 9 张，平均值为 10，则差值为-1，表示需要移入 1 张纸牌。

3. 前缀和数组构造

vector<int> prefix(n);
prefix[0] = cards[0];
for (int i = 1; i < n; i++) {
prefix[i] = prefix[i-1] + cards[i];
}

• 前缀和的意义：prefix[i]表示从第 1 堆到第i堆的总差值。例如，若前 3 堆的差值分别为-1, -2, 7，则prefix[2] = -1 + (-2) + 7 = 4，表示前 3 堆总共多出 4 张纸牌，需要后续堆来平衡。

4. 统计非零元素数量

int count = 0;
for (int i = 0; i < n; i++) {
if (prefix[i] != 0) {
count++;
}
}
cout << count << endl;

• 移动次数的来源：前缀和数组中的每个非零元素代表一个必须进行的移动步骤。例如：
  • 若prefix[i]为正，表示前i堆需要移出prefix[i]张纸牌；
  • 若为负，表示前i堆需要移入abs(prefix[i])张纸牌。
  • 每次移动可以消除一个非零的前缀和值，因此非零元素的数量即为最少移动次数。

三、数学证明与示例验证

1. 数学证明

• 前缀和的性质：
  由于所有堆的总差值为 0（总和为sum – n*avg = 0），前缀和数组的最后一个元素prefix[n-1]必为 0。
• 移动次数的推导：
  假设前缀和数组中有k个非零元素，每次移动可以消除一个非零值（例如，将prefix[i]的不平衡转移到下一堆），最终所有前缀和都变为 0，因此需要k次移动。

2. 示例分析（输入：4 9 8 17 6）

• 步骤 1：计算平均值
  sum = 9+8+17+6 = 40，avg = 40/4 = 10。
• 步骤 2：构造差值数组
  cards = [9-10, 8-10, 17-10, 6-10] = [-1, -2, 7, -4]。
• 步骤 3：计算前缀和数组
  prefix[0] = -1
  prefix[1] = -1 + (-2) = -3
  prefix[2] = -3 + 7 = 4
  prefix[3] = 4 + (-4) = 0
  非零元素为-1, -3, 4，共 3 个，对应移动次数 3。

3. 移动过程与前缀和的关系

• 第一次移动：从堆 3 移 4 张到堆 4。
  差值数组变为[-1, -2, 3, 0]，前缀和变为[-1, -3, 0, 0]。此时非零元素减少 1 个。
• 第二次移动：从堆 3 移 3 张到堆 2。
  差值数组变为[-1, 1, 0, 0]，前缀和变为[-1, 0, 0, 0]。非零元素再减少 1 个。
• 第三次移动：从堆 2 移 1 张到堆 1。
  差值数组全为 0，前缀和全为 0。移动次数为 3。

四、时间复杂度分析

• 输入处理：O(n)
• 平均值计算：O(1)
• 差值数组构造：O(n)
• 前缀和数组构造：O(n)
• 非零元素统计：O(n)
• 总时间复杂度：O (n)，可高效处理题目给定的n≤100的数据规模。

五、关键思想总结

通过这种方法，我们无需模拟具体的移动过程，而是通过数学分析直接得出最优解，体现了算法设计中的抽象思维和问题转化能力。