自动搬运

查看原文

来自洛谷，原作者为

	SBofGaySchool SB of gay school BU PA anything!

搬运于2025-08-24 21:44:55，当前版本为作者最后更新于2021-12-29 11:37:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我来一篇构造的题解吧。

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.构造方式

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

• 情况一：任何帮派中牛的数量不超过总牛数（不考虑一号帮派）的一半（向上取整）

  • 当草场上没有牛的时候： 选择序号最小的帮派，把所有牛都放上去。这样做不会对各个帮派中牛的数量造成影响；

  • 当草场上有牛的时候： 此时要考虑派哪个帮派的牛去打架。根据刚才证明的结论，只要打完架之后没有破坏条件 $X \le \lceil S/2 \rceil$，我们最终一定能够让剩下的牛数最少。我们先尝试选择下一个序号最小的帮派中的一头牛去草场上打架；

    • 如果这样打完架之后条件 $X \le \lceil S/2 \rceil$ 未被破坏： 那么我们这么做不会改变剩余牛数（剩下的牛数还是可以做到尽量少），还满足了字典序尽量小；

    • 如果这样打完架之后条件 $X \le \lceil S/2 \rceil$ 被破坏了： 这意味着我们必须从当前牛数最多的帮派中找牛去打架（根据上文对结论的证明，这样构造不会破坏条件）。我们就撤销刚才的决策，改为从当前牛数最多的帮派中找牛去打架。

• 情况二：牛数最多的那个帮派中牛的数量超过总牛数（不考虑一号帮派）的一半（向上取整）

  • 当草场上没有牛的时候： 选择序号最小的帮派，把所有牛都放上去；

  • 当草场上有牛的时候： 如果这个帮派不是牛数最多的帮派，为了让剩余牛数尽量少，我们就要从牛数最多的帮派中派牛去打架；否则，我们只需要让之后的帮派依次去打架即可。

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

• 当草场上没有牛的时候： 选择序号最小的帮派，把所有牛都放上去；

• 当草场上有牛的时候： 先尝试选择下一个序号最小的帮派中的一头牛去草场上打架。如果发现这么做会使得不在草场上的帮派中牛数最多的帮派中牛的数量超过总牛数一半（对于情况二而言，只要当前草场上的帮派的牛数不是最多的，此条件一定成立），就需要从牛数最多的那个帮派中选一头牛去草场上打架。

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

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

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;
}