[NOIP2002-提高] 均分纸牌

题目描述

$N$ 堆纸牌（总数为 $N$ 的倍数），每次从一堆取任意张移到相邻堆，求使每堆等于平均值的最少移动次数（ $N \le 100$ ）。

思路

前 $i$ 堆的盈余 $S_i$ 必须经边 $(i,i+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#!/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-10-02 04:52
# update_at: 2026-10-04 10:27

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    piles = [next(data) for _ in range(n)]
    avg = sum(piles) // n  # 每堆最终张数：总数必为 n 的倍数

    # 贪心：1 号堆只能把牌推给 2 号，其差额必须一次搬完；搬完后 1 号永久定型。
    # 依次处理到 n-1 号，每堆不等于 avg 就做一次移动，把差额整体推给右邻。
    moves = 0
    for i in range(n - 1):
        if piles[i] != avg:
            moves += 1                       # 一次移动可搬任意张数，只计次数
            piles[i + 1] += piles[i] - avg   # 右邻接管差额，本堆定型为 avg
    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/**
 * 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-06 12:40
 * update_at: 2026-10-06 12:40
 */
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 105;

ll a[MAXN]; // 每堆纸牌数量

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

    int n;
    cin >> n;
    ll sum = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        sum += a[i];
    }
    ll avg = sum / n; // 每堆最终张数：总数必为 n 的倍数

    // 贪心：第 i 堆只能与 i+1 堆交互，其差额必须一次搬完；搬完后第 i 堆永久定型为 avg。
    // 依次处理到第 n-1 堆，每堆不等于 avg 就做一次移动，把差额整体推给右邻。
    int moves = 0;
    for (int i = 1; i <= n - 1; ++i) {
        if (a[i] != avg) {
            moves++;              // 一次移动可搬任意张数，只计次数
            a[i + 1] += a[i] - avg; // 右邻接管差额，本堆定型为 avg
        }
    }
    cout << moves << '\n';
    return 0;
}

[NOIP2002-提高] 均分纸牌

目录

题目描述

思路

参考代码