专栏文章

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

NN1tr0us_Acid
P11467题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip5j18q
此快照首次捕获于
2025/12/03 06:30
3 个月前
此快照最后确认于
2025/12/03 06:30
3 个月前
查看原文
非常好的贪心，使我的大脑旋转。

Solution\texttt{Solution}

因为不论每个城堡的耗费兵力多少，它们每回合对总兵力的贡献都是 11，所以我们肯定要按兵力从小到大攻占城堡。
其次，如果在某一回合我们的总兵力已经可以攻占某一座城堡，那么立刻攻占该城堡一定优于在若干回合后再攻占该城堡，因为城堡消耗兵力不变，越早攻占，这座城堡就会提供越多的贡献。
那么就很好写了，我们预处理出 timtim 和 lesles 两个数组，timitim_i 表示最早在第几回合可以攻下 ii 座城堡，lesiles_i 表示攻下之后还剩多少兵力，然后对于每种情况进行模拟即可。
注意两个特判：
  1. 如果攻占了所有城堡仍不能超过对手，就是 −1-1。
  2. 如果一个城堡都不用攻占，即 x>yx > y，就只用 11 回合。

Code\texttt{Code}

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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...