CF2037F Ardent Flames

题目传送门

大致思路

显然随着攻击次数增多,击败的敌人会更多,满足单调性,考虑二分
接下来问题就是在确定攻击次数为 $x$ 的情况下,能否击败超过 $k$ 个敌人
对于每个敌人在的位置 $pos$ 和 血量 $hp$ ,以及其与攻击的位置 $p$ 的距离 $dis$,可以得出:

$$hp≤x(m-dis) $$

$$dis≤m-hp/x $$

记$d=m-hp/x$ ,也就是攻击位置 $p$ 在$[pos-d,pos+d]$内,则该敌人会被击败
这里用到差分,将 $[pos-d,1]$ 和 $[pos+d+1,-1]$加入数组 $a$
前者表示攻击位置到达 $pos-d$ 击败的敌人会 $+1$,后者表示超过 $pos+d$ 击败的敌人会 $-1$

void solve() {
    int n,m,k;
    cin >> n >> m >> k;
    vector<int> hp(n);
    for (int i=0;i<n;i++) cin >>hp[i];
    vector<int> pos(n);
    for (int i=0;i<n;i++) cin >> pos[i];
    int left=1,right=1e9,ans=-1;
    auto check=[&](int x)->bool {
        vector<array<int,2>> a;//斩杀线
        for (int i=0;i<n;i++) {
            int dis=m-(hp[i]+x-1)/x;
            if (dis<0) continue;
            a.pb({pos[i]-dis,1});
            a.pb({pos[i]+dis+1,-1});
        }
        int cnt=0;
        sort(all(a));
        for (auto [u,v]:a) {
            cnt+=v;
            if (cnt>=k) return true;
        }
        return false;
    };
    while (left<=right) {
        int mid=left+(right-left)/2;
        if (check(mid)) {
            ans=mid;
            right=mid-1;
        }
        else left=mid+1;
    }
    cout << ans<<el;

}