题解 P3064 【[USACO12DEC]Gangs of Istanbull/Cowstantinople G】

· · 题解

我来一篇构造的题解吧。

1.题目思路

本题的要求有二：

  1. 一号帮派剩余牛数尽量多；
  2. 在满足要求一的情况下，字典序尽量小。

我们首先思考如何构造能够使得一号帮派剩余牛数最多。为了达到这个目的，我们 要让其他帮派的牛相互打架，剩下尽量少的牛去和一号帮派打。

考虑 除了一号帮派之外 的其他牛。在初始状态下有两种情况，我们分别讨论。

设总牛数为 S，当前牛数最多的帮派牛数为 X，则这种情况可以表示成 X \le \lceil S/2 \rceil。在这种情况下我们可以证明，存在一种构造，使得这些牛打完架之后一头不剩（偶数）或只剩一头（奇数）。我们用数学归纳法来证明这个结论。

  1. 当 S=2 时，一共只有两头牛，满足条件的情况只有一个，即一头 A 帮派的牛与一头 B 帮派的牛。让他们打架后，一头牛都不剩，结论成立；
  2. 当 S=3 时，在满足条件的情况下，牛的帮派可以被表示为 AAB 或 ABC。选取 A 帮派的牛和另一个帮派的牛打架，最终只剩一头牛，结论成立；
  3. 若 S=K-2 时结论成立，则当 S=K 时，我们选择当前牛数最多的帮派（设牛数为 X，此时满足X \le \lceil S/2 \rceil）中的一头牛和随便一个其他帮派的一头牛打架，则打完架后该帮派牛的数量 X'=X-1，同时 S=K-2，仍然满足 X' \le \lceil S/2 \rceil ，情况转换为了 S=K-2 时的情况。故若 S=K-2 时结论成立，则当 S=K 时结论仍成立。

综上，我们证明了这个结论。

根据鸽笼原理，最后剩下的帮派一定是一开始牛数最多的那个帮派。此时最优策略就是让其他牛都去和这个帮派的牛打架，才能让这个帮派尽量少剩下牛。

2.构造方式

除了找出剩余牛数最少的构造方式，我们还需要考虑到字典序最小这个要求。对于上述两种情况，我们分别进行构造，使得在其他帮派的牛相互打架之后剩下的牛尽量少的前提下，字典序尽量小。

总结上述情况，我们可以得到以下具体的构造方式：

打完架之后，最后再让一号帮派的牛去草场上，就可以让一号帮派剩余牛数尽量多，同时让其他帮派打架顺序的字典序尽量小了。

这里还有最后一点需要注意的地方：为了让字典序最小，我们可以在不影响结果的基础上，先让一号帮派的牛去草场上，之后再让其他帮派去打架，最后再安排剩下的一号帮派的牛去草场上。

3.代码实现

#include <bits/stdc++.h>
using namespace std;
#define MAXN 105
int N, M, a[MAXN];
// f为下一个帮派序号，sum为剩余牛总数，maxi为不在草场上的帮派中牛数最多的帮派序号
// cur为当前草场上的帮派序号，cnt为当前草场上牛的数量
int f, sum, maxi, cur, cnt;
// 重新计算上述各项变量
void calc() {
    f = sum = maxi = 0;
    for (int i = 2; i <= M; i++) {
        if (a[i] <= 0) {
            continue;
        }
        if (!f) {
            f = i;
        }
        sum += a[i];
        if (!maxi || a[i] > a[maxi]) {
            maxi = i;
        }
    }
}
int main() {
    cin >> N >> M;
    for (int i = 1; i <= M; i++) {
        cin >> a[i];
    }
    calc();
    // 先计算其他帮派打完架之后最少会剩多少头牛
    int l = max(a[maxi] - (sum - a[maxi]), sum % 2);
    if (a[1] <= l) {
        cout << "NO" << endl;
        return 0;
    }
    cout << "YES" << endl << a[1] - l << endl;
    // 为了让字典需最小，在不影响结果的情况下，先让一号帮派的牛去草场上
    while (a[maxi] > cnt + sum - a[maxi]) {
        cout << 1 << endl;
        a[1]--;
        cur = 1;
        cnt++;
    }
    if ((cnt + sum) % 2) {
        cout << 1 << endl;
        a[1]--;
        cur = 1;
        cnt++;
    }
    // 在还剩余牛的情况下，让其他帮派的牛打架
    while (sum) {
        if (cnt) {
            // 如果草场上有牛
            if (a[maxi] > cnt + sum - a[maxi] - 2) {
                // 如果派其他帮派的牛去打架会导致剩余牛数最多的帮派牛数超过总牛数的一半
                // 就需要派剩余牛数最多的帮派中的一头牛去草场上打架
                cout << maxi << endl;
                a[maxi]--;
            } else {
                // 否则，派任何帮派的牛都可以
                // 为了字典序号最小，我们派下一个序号最小的帮派中的一头牛去打架
                cout << f << endl;
                a[f]--;
            }
            cnt--;
            if (!cnt) {
                cur = 0;
            }
        } else {
            // 如果草场上没有牛，直接把下一个帮派中所有牛派去草场上
            cur = f;
            cnt = a[f];
            while (a[f]--) {
                cout << f << endl;
            }
        }
        // 重新计算派完牛之后各个帮派牛的数量
        calc();
        if (sum == a[maxi] && (!cnt || cur == 1)) {
            break;
        }
    }
    // 最后再让一号帮派的牛去草场上
    while (a[1]--) {
        cout << 1 << endl;
    }
    while (a[f]--) {
        cout << f << endl;
    }
    return 0;
}