【例6.2】均分纸牌(Noip2002)

题目描述

有 $n$ 堆纸牌，第 $i$ 堆有 $a_i$ 张，总数保证是 $n$ 的倍数。每次可以从一堆取若干张移到相邻的一堆（第 $1$ 堆只能移给第 $2$ 堆，第 $n$ 堆只能移给第 $n-1$ 堆）。输入 $n$ 和 $a_1 \ldots a_n$ （ $1 \leqslant n \leqslant 100$ ， $1 \leqslant a_i \leqslant 10000$ ），输出使每堆牌数都相等的最少移动次数。样例：输入 4 / 9 8 17 6，输出 3。

思路

设平均值 $\bar a$ ，第 $i$ 堆的偏差 $d_i = a_i - \bar a$ 。跨过第 $i$ 条边界（ $i \to i+1$ ）的净牌数被两端盈亏唯一确定，恰好等于前缀和 $s_i = d_1 + \cdots + d_i$ ，所以 $s_i \ne 0$ 时这条边界至少要搬一次，而每条非零边界各搬一次就可以做到（把同号的区间接力推平），因此答案是 $s_1, \ldots, s_{n-1}$ 中非零的个数。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 05:05
# update_at: 2026-09-30 05:05

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    cards = [next(data) for _ in range(n)]

    # 每堆的盈余（正数表示多出来，负数表示还缺）：目标就是让每一堆盈余归零
    diff = [x - sum(cards) // n for x in cards]

    # 前缀和 s[i] = 前 i 堆的盈余之和。相邻两堆之间必须流过的牌数恰好是 |s[i]|，
    # 所以不管怎么调度，第 i 次"跨 i/i+1 边界的移动"都少不了；总次数 = 非零前缀和个数。
    prefix = 0
    moves = 0
    for i in range(n - 1):  # 最后一条边不用管：总盈余为 0，前 n-1 个前缀为 0 即全部为 0
        prefix += diff[i]
        moves += prefix != 0

    print(moves)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
39
40
41
42
43
44
45
46
47/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 09:17
 * update_at: 2026-10-05 09:17
 */
// main.cpp：均分纸牌，答案等于「偏差前缀和非零」的个数。
#include <iostream>
using namespace std;

const int MAXN = 105;

typedef long long ll;

ll n;
ll a[MAXN];    // a[i] 表示第 i 堆纸牌的初始张数
ll diff[MAXN]; // diff[i] = a[i] - 平均值，表示第 i 堆多出（正）或缺少（负）的张数

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

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

    ll avg = sum / n; // 纸牌总数保证是 n 的倍数

    // 每条相邻边界 i/i+1 上净流过的牌数被两端盈亏唯一确定，恰好等于偏差的前缀和；
    // 前缀和不为零就说明这条边界必须搬一次，所以答案就是非零前缀和的个数。
    ll prefix = 0;
    ll moves = 0;
    for (ll i = 1; i <= n - 1; i++) {
        diff[i] = a[i] - avg;
        prefix += diff[i];
        if (prefix != 0) {
            moves++;
        }
    }

    cout << moves << endl;
    return 0;
}

【例6.2】均分纸牌(Noip2002)

目录

题目描述

思路

参考代码