[NOIP 2002 提高组] 均分纸牌(Equalize Cards) 题解

思路分析

计算出平均纸牌数 $avg = \frac{1}{N}\sum_{i=1}^N A_i$。从左到右扫描第 $1 \sim N-1$ 堆：若当前 $A_i \ne avg$，则第 $i$ 堆与第 $i+1$ 堆之间必然发生一次净转移，令 ans++ 且 A[i + 1] += A[i] - avg（允许中间计算暂时为负，等价于先由右侧移向左侧）。总时间复杂度 $O(N)$。

参考代码

#include <iostream>
using namespace std;

int a[105];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    int sum = 0;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        sum += a[i];
    }
    int avg = sum / n;
    int ans = 0;
    for (int i = 1; i < n; ++i)
    {
        if (a[i] != avg)
        {
            a[i + 1] += a[i] - avg;
            ++ans;
        }
    }
    cout << ans << "\n";
    return 0;
}