题解：P11467 网瘾竞赛篇之 generals 大法好

· · 题解

非常好的贪心，使我的大脑旋转。

\texttt{Solution}

因为不论每个城堡的耗费兵力多少，它们每回合对总兵力的贡献都是 1，所以我们肯定要按兵力从小到大攻占城堡。

其次，如果在某一回合我们的总兵力已经可以攻占某一座城堡，那么立刻攻占该城堡一定优于在若干回合后再攻占该城堡，因为城堡消耗兵力不变，越早攻占，这座城堡就会提供越多的贡献。

那么就很好写了，我们预处理出 tim 和 les 两个数组，tim_i 表示最早在第几回合可以攻下 i 座城堡，les_i 表示攻下之后还剩多少兵力，然后对于每种情况进行模拟即可。

注意两个特判：

  1. 如果攻占了所有城堡仍不能超过对手，就是 -1。
  2. 如果一个城堡都不用攻占，即 x > y，就只用 1 回合。

\texttt{Code}

#include <bits/stdc++.h>

using namespace std;

#define int long long

int x, y, n;

const int N = 2e5 + 10, inf = 0x3f3f3f3f;

int tt;

int a[N], tim[N], les[N];

signed main(void) {
    cin >> tt;

    while (tt --) {
        cin >> n >> x >> y;

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

        sort(a + 1, a + n + 1); // 一定要记得排序！

        if(x + n <= y) { // 特判1
            puts("-1");

            continue;
        }

        if(x > y) { // 特判2
            puts("1");

            continue;
        }

        int nowx = 0, kx = x;

        for (int i = 1; i <= n; i ++) {
            if(a[i] <= nowx) {
                tim[i] = tim[i - 1] + 1;

                nowx -= a[i];
                nowx += kx;

                les[i] = nowx;

                kx ++;

                continue;
            }

            int del = (a[i] - nowx) / kx + ((a[i] - nowx) % kx != 0);

            nowx += del * kx + kx;
            nowx -= a[i];
            kx ++;

            tim[i] = tim[i - 1] + del + 1;
            les[i] = nowx;
        }

        int ans = inf;

        for (int i = y - x + 1; i <= n; i ++) { // 只有当 x + i > y 时，才有可能超过对手，所以 i 从 y - x + 1 开始。
            int nowy = y * tim[i];

            int del = nowy - les[i];

            int wil = del / (x + i - y) + 1;

            ans = min(ans, tim[i] + wil);
        }

        cout << ans << endl;
    }
}