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

No_commander · 2024-12-26 21:30:42 · 题解

神奇模拟。

把城堡需要的兵力排个序，当 t1e 的兵力能买消耗最小的城堡时，判断一下不买该城堡的答案，与全局答案取 \min，然后直接默认买掉（如果不买更优那么后面就不会再更新全局答案），循环模拟一下就行。

大概就是这样：

il void mian(){
    read(n, x, y), readArr(a + 1, n);
    if (x + n <= y) return cout << "-1", void();
    if (x > y) return cout << "1", void();
    sort(a + 1, a + n + 1);
    int b1 = 0, b2 = 0, ans = 0, ret = inf / 2;//b1 是 t1e 的兵力，b2 是对手的兵力
    L(i, 1, n){
        int tim = (a[i] - b1 - 1) / x + 1, t = inf / 3;
        if (b1 >= a[i]) tim = 0;
        if (x > y) t = (b2 + 1 - b1 - 1) / (x - y) + 1;
        ckmin(ret, ans + t), ans += tim + 1, b1 += tim * x, b2 += tim * y;
        b1 -= a[i], b1 += x, x++, b2 += y;
    }
    write(min(ret, ans + (b2 + 1 - b1 - 1) / (x - y) + 1));
}