参考题解

管理员提示：该题解为AI自动生成，请注意甄别

均分纸牌题解（含思路 + 代码 + 图解）

题目传送门

均分纸牌

思路分析

一、平均分与差值

设：

表示每堆应有的平均张数。

二、关键观察

我们希望从左到右（或右到左）平衡所有堆，使它们都变成 avg。

对任意前缀：

• 若 ( s[i] > 0 )：前 i 堆比平均值多 ( s[i] ) 张 → 需要往右送；
• 若 ( s[i] < 0 )：前 i 堆比平均值少 ( -s[i] ) 张 → 需要从右边借。

三、简单解法（贪心 + 模拟）

我们从左到右扫描：

• 若前一堆少，就从右边借；
• 若前一堆多，就往右边送。
• 若右边不够，就一路向右找可以借的堆，然后回溯调整。

这种方法能保证：

• 所有移动合法（不会负数）；
• 总移动次数最少；
• 输出字典序最小。

四、算法步骤

1. 计算平均值 avg。

2. 从第 2 堆开始向右遍历：

   • 如果前一堆 < avg：向右借牌，必要时跨多堆。
   • 如果前一堆 > avg：向右送出多余的牌。

3. 每次操作记录 (from, to, num)。

4. 输出所有移动。

示例过程（样例 3）

输入：

4
0 0 0 4

平均数 avg = 1。

输出：

3
4 3 3
3 2 2
2 1 1

复杂度分析

代码实现

#include <bits/stdc++.h>
using namespace std;

const int N = 300005;

int n;                        // 堆的数量
int a[N];                     // 每堆纸牌数量
int ans_from[N], ans_to[N];   // 记录每次移动的来源和目标堆
int ans_num[N];               // 记录每次移动的数量

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    int total = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        total += a[i];
    }

    int avg = total / n;  // 每堆应有的平均纸牌数
    int cnt = 0;          // 移动次数计数器

    // 从第二堆开始依次检查前一堆的状态
    for (int i = 2; i <= n; ++i) {

        // ==========================
        // 情况 1：前一堆纸牌少于平均值 → 需要从右边借牌
        // ==========================
        if (a[i - 1] < avg) {
            int need = avg - a[i - 1]; // 当前堆还缺多少

            // ✅ 如果右边一堆够借
            if (a[i] >= need) {
                // 从第 i 堆拿 need 张放到 i-1 堆
                ans_from[++cnt] = i;
                ans_to[cnt] = i - 1;
                ans_num[cnt] = need;

                // 更新当前状态
                a[i] -= need;
                a[i - 1] = avg;
            }

            // 🚨 如果右边这一堆不够借，要向更右边连续借
            else {
                int start = i - 1;   // 起始点：第一个缺牌的堆
                // balance：当前这段的“盈余量”（负数代表仍然不够）
                int balance = a[i] + a[i - 1] - 2 * avg;

                // 一直往右找，直到 balance ≥ 0（表示总算够补齐左边了）
                while (i <= n) {
                    ++i;
                    if (balance + a[i] >= 0) break;
                    balance = balance + a[i] - avg;
                }

                // 现在 i 表示右端界（balance 足够的位置）
                --i;

                // 把多余 balance 调整，使右边多余转为平衡
                a[i] -= balance;
                a[i + 1] += balance;

                ans_from[++cnt] = i + 1;
                ans_to[cnt] = i;
                ans_num[cnt] = -balance;

                // 🔁 回溯，从右往左补齐中间每一堆
                for (int j = i; j > start; --j) {
                    int give = a[j] - avg; // 当前堆多出的部分（可能是负数）

                    // 把多余的牌送到左边一堆
                    ans_from[++cnt] = j;
                    ans_to[cnt] = j - 1;
                    ans_num[cnt] = give;

                    // 同步更新数组
                    a[j - 1] += give;
                    a[j] = avg;
                }

                ++i; // 继续下一堆的判断
            }
        }

        // ==========================
        // 情况 2：前一堆纸牌多于平均值 → 把多余的往右送
        // ==========================
        else if (a[i - 1] > avg) {
            int give = a[i - 1] - avg; // 多出的数量

            // 从左边往右送
            ans_from[++cnt] = i - 1;
            ans_to[cnt] = i;
            ans_num[cnt] = give;

            // 更新当前状态
            a[i] += give;
            a[i - 1] = avg;
        }

        // ==========================
        // 情况 3：刚好等于平均值 → 不需要操作
        // ==========================
    }

    // ==========================
    // 输出所有操作
    // ==========================
    cout << cnt << "\n";
    for (int i = 1; i <= cnt; ++i) {
        cout << ans_from[i] << " " << ans_to[i] << " " << ans_num[i] << "\n";
    }

    return 0;
}

小结

📎 拓展思考

• 可以用 前缀和 + 贪心 推出等价的最优移动数公式：$$\text{最少移动次数} = \sum_{i=1}^{n-1} |s[i]|$$ 但那只求次数，不给出方案。
• 本题代码通过模拟「真实移动」，同时输出合法方案。