原题大意

一条线上有N个怪兽，第i个怪兽有hi格血条，我们每次可以对其中一个怪发动攻击，使他损失A格血，同时，除他以外的怪兽要损失B格血（A>B），问最少攻击几次使得怪兽全部gg。

算法分析

贪心的想，每次让血最多的怪受到直接攻击，直到所有怪都完蛋，下面考虑优化，每次攻击每个怪都会受到B的伤害，其中被直接攻击到的还要受到（A—B）的额外伤害，假设攻击次数为t，enough(t) = yes / no 为（t次攻击成功消灭怪兽）答案。t为单调函数，可以二分来做，t次攻击的额外伤害次数应该等于t，即为 ∑⌈(hi −B ×T)/(A−B)⌉ = t。

程序代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
int n;
ll a, b;
ll h[maxn];
ll check(ll m){
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        if((h[i] - b * m) > 0)
            ans+=ceil((double)(h[i] - b * m) / (a-b));
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> a >> b;
    for(int i = 1; i <= n; i++){
        cin >>  h[i];
    }
    ll l = 1, r = 1e9;
    while(l < r){
        ll mid = l+(r-l)/2;
        if(check(mid) > mid) l = mid+1;
        else r = mid;
    }

    cout << l << endl;
    return 0;
}