P11467 网瘾竞赛篇之 generals 大法好

网瘾竞赛篇之 generals 大法好

题目描述

t1e 同学沉迷于打 generals 的 1v1 模式，他将游戏简化为以下内容：

初始时 t1e 有一座城堡，每回合结束时会生产 $x$ 单位的兵力，他的对手也有一座城堡，每回合结束时会生产 $y$ 单位的兵力，初始时（第 $0$ 回合）双方的兵力都为 $0$。

有 $n$ 座其他城堡可以被 t1e 占领，t1e 每个回合开始时可以攻占最多 $1$ 个城堡，占领第 $i$ 个城堡需要消耗 $a_i$ 单位的兵力，从占领后的下一个回合开始，该城堡每回合结束时为 t1e 生产 $1$ 个单位的兵力。

t1e 同学想知道最早在第多少个回合，他的兵力能超过对手的兵力。

如果永远无法超过，输出 $-1$。

输入格式

本题有多组数据。

第一行一个正整数 $T$，表示数据组数。

对于每组数据：

第一行输入三个整数，分别代表 $n,x,y$。

第二行 $n$ 个整数代表 $a_i$。

输出格式

对于每组数据：

一行一个整数，代表 t1e 的兵力超过对手兵力的最小回合数。

如果永远无法超过，输出 $-1$。

样例 #1

样例输入 #1

4
1 1 1
1
6 1 2
1 1 4 5 1 4
2 1 3
1 1
1 3 2
1

样例输出 #1

4
7
-1
1

提示

对于第一组数据，t1e 的最优操作过程如下：

注意：t1e 在第 $2$ 回合开始时占领了 $1$ 号城堡。

$1\le T\le 100$，$1\le n,\sum n\le 2\times 10^5$，$1\le x,y,a_i\le 10^5$。

思路：

见注释。
先算出占领每个城堡（按升序排列）时的状态，然后如果x>y就可以计算占领答案，最后保留最小答案。

代码：

#include <bits/stdc++.h>
#define endl '\n'
#define int long long 
#define pb push_back
#define pii pair<int,int>
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
#define FU(i, a, b) for(int i = (a); i <= (b); ++ i)
#define FD(i, a, b) for(int i = (a); i >= (b); -- i)
using namespace std;
int a[200005];
int t[200005]; //占领第i座城堡时的回合数
int g[200005]; //占领第i座城堡后剩余的兵力
void solve() {
    t[0]=0,g[0]=0;
    int n,x,y;
    cin>>n>>x>>y;
    FU(i,1,n){
        cin>>a[i];
    }
    if(x>y){cout<<"1\n";return;}
    if(x+n<=y){cout<<"-1\n";return;}
    sort(a+1,a+n+1);
    
    int nx=x;
    int ans = 1e18;
    for(int k=1;k<=n;k++){
        t[k] = t[k-1] + max(0LL,(a[k] - g[k-1] + nx -1 )/nx) +1;
        //此处末尾必须+1，是因为占领也需要一个回合。 除法上取整，然后与0ll取max，因为上一次保留的兵力可能大于占领城堡所需。
        g[k] = g[k-1] + (t[k]-t[k-1])*nx -a[k];
        nx++;
        if(nx > y)  ans = min(ans,t[k] + (t[k]*y-g[k])/(nx-y)+1);
    }
    // for(int i=1;i<=n;i++){
    //     cout<<"- "<<i<<" "<<t[i]<<" "<<g[i]<<endl;
    // }
    cout<<ans<<"\n";

}

signed main() {
    cin.tie(0)->ios::sync_with_stdio(0);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}