题解 P1031 [NOIP2002 提高组] 均分纸牌

link

贪心

题中描述

每一堆牌只能移动若干张牌到相邻的牌堆上

确定了局部最优解必定能推导出全局最优解。

易知均分完后，每堆牌的数量都为纸牌总数的平均数 \(\mathrm{arg}\) 。

所以我们可以预处理每堆牌跟 \(\mathrm{arg}\) 的差距

for (int i = 1; i <= n; ++i) sum += a[i];
int arg = sum / n;
for (int i = 1; i <= n; ++i) a[i] -= arg;

显然可以分三种情况：

• 当 \(a_i = 0\) 时，此时这堆牌不需要移动
• 当 \(a_i < 0\) 时，这堆牌需要从其他堆拿过来
• 当 \(a_i > 0\)​ 时，这堆牌需要全部给其他牌

显然我们可以保证 \(1 \sim i - 1\) 已经是局部最优解。于是第 \(i\) 堆只需要给第 \(i + 1\) 堆或从第 \(i + 1\)​ 堆拿过来。

写出代码

for (int i = 1; i <= n; ++i) {
    if (a[i] == 0) continue; // 不需要移动
    else if (a[i] > 0) { // 大于0
        a[i + 1] += a[i]; // 给后面的人
        ans ++; // 次数加1
    }else {
        a[i + 1] -= (-a[i]); // 从后面补到0
        ans ++; // 次数加1
    }
}

由于 \(a_{i+1} - (-a_i)\) 等于 \(a_{i + 1} + a_i\) 。

于是 \(a_i > 0\) 和 \(a_i < 0\) 时代码一样

可以简化代码为：

for (int i = 1; i <= n; ++i) {
    if (a[i] == 0) continue;
    a[i + 1] += a[i];
    ans ++;
}

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

int n;
int a[N];
int sum = 0, ans = 0;

int main() {
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i], sum += a[i];

    int arg = sum / n;
    for (int i = 1; i <= n; ++i) a[i] -= arg;
    for (int i = 1; i <= n; ++i) {
        if (!a[i]) continue;
        a[i + 1] += a[i];
        ans ++;
    }
    cout << ans;
    return 0;
}