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

_nothingGG · 2025-07-09 13:02:09 · 题解

一眼贪心题。

注意到：

• 如果 x>y 那么第一个回合就能超过。

• 如果 x+n\le y 那么无论如何无法超过。

• 否则 x+n>y 也就是说只要等待时间够长就能超过。

那么该按照什么顺序攻占城堡呢？

城堡（以下简称“塔”）的费用越小越好：从加兵力的角度看，塔的费用越小，那么你花费越小，并且你能更快地攒够兵力，也就更快地能让塔工作。

因此，可以将塔的花费按照从小到大排序，依次占领，只要能占就占。

attention：如果此时的 x+k>y 了，也就是说可以现在就放弃继续开塔，直接蹲兵力，此时是可以直接算出还要多久才能超过对手的，所以要把这些满足 x+k>y 的情况考虑进去，而不是开完所有塔才是最好的！

于是：上代码！

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int cal(int x,int y){return (x+y-1)/y;}
signed main(){
    int T;cin>>T;
    while(T--){
        int n,x,y,a[N];
        cin>>n>>x>>y;
        for(int i=1;i<=n;i++)cin>>a[i];
        if(x+n<=y){puts("-1");continue;}
        if(x>y){puts("1");continue;}
        sort(a+1,a+n+1);
        int rlt=0x3f3f3f3f,turns=0;
        int me=0,other=0;
        for(int i=1;i<=n;i++){
            if(x>y)rlt=min(rlt,turns+cal(other-me+1,x-y));
            int t=max(0ll,cal(a[i]-me,x));
            turns+=t+1;
            other+=(t+1)*y;
            me+=(t+1)*x-a[i];
            x++;
        }
        rlt=min(rlt,turns+cal(other-me+1,x-y));
        cout<<rlt<<endl;
    }
    return 0;
}