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

_std_O2 · 2025-03-09 14:46:02 · 题解

P11467题解

考虑贪心，每次开所耗兵力最小的塔，当 x>y 时判断是否再开新的塔。

证明

假设每次不是开所耗兵力最小的塔，又因为只能当 x>y 时 t1e 同学的兵力才能超过对面。则所让 x>y 时所需的回合数一定大于每次开所耗兵力最小的塔所需的回合数，故假设不成立。

判断有无解

显然只有当 x+n>y 时 t1e 同学的兵力才能超过对面。当 x+n \le y 时 t1e 同学的兵力永远无法超过对面。

Code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int n,x,y,T,a[300005];
signed main(){
    cin>>T;
    while(T--){
        int ans=1e18;
        cin>>n>>x>>y;
        int army=0,num=0,add=x;//army 为现有兵力，num为回合数，add 为每回合的产兵数
        for(int i=1;i<=n;i++) cin>>a[i];
        if(x>y) {
            cout<<1<<endl;
            continue;
        }
        if(x+n<=y){
            cout<<-1<<endl;
            continue;
        }
        sort(a+1,a+n+1);
        for(int i=1;i<=n;i++){
            num=max(num+1,(int)ceill((a[i]-army)*1.0/add)+1);
            int cnt=add*num+army;
            add++,army=cnt-a[i]-add*num;
            if(add>y)ans=min(ans,army/(y-add)+1);//判断是否再多开塔
        }
        cout<<ans<<endl;
    }
}