贪心、二分答案

答案显然具有单调性，考虑二分答案 $mid$，难点在于检查。检查时不可提前选定 $p$，应该判定是否存在能够在 $mid$ 次攻击内杀死 $k$ 个敌人的 $p$ 作为攻击点。

对于血量为 $h_i$，位置为 $x_i$ 的敌人 $i$，若其在 $mid$ 次攻击后死亡，能够将其击杀的攻击点 $p$ 必定满足 $\dfrac{h_i}{m - |p - x_i| } \leq mid$，这个式子由于 $p$ 的值不固定而难以分析。转换思路，因为 $mid$ 为定值，将 $mid$ 换到分母上得到 $\dfrac{h_i}{mid} \leq m - |p - x_i|$，又因为 $m$ 为定值，将式子化为 $|p - x_i| \leq m - \dfrac{h_i}{mid}$。能够看出对于给定的值 $mid$，能够在至多 $mid$ 次攻击内击杀 $i$ 的位置 $p$ 形成一段连续区间，为了方便计算再给 $\dfrac{h_i}{mid}$ 套一个上取整，因为 $p$ 是整数，这不影响答案计算。最终得到如下式子。

$$|p - x_i| \leq m - \left\lceil \dfrac{h_i}{mid} \right\rceil$$

首先排除不能在至多 $mid$ 次攻击内杀死的敌人。对于能够在至多 $mid$ 次攻击内杀死的敌人，第 $i$ 个敌人贡献了一个区间 $[l_i,r_i]$，如果选定的 $p \in [l_i,r_i]$ 就可以杀死第 $i$ 个敌人。

问题转化为对于序列 $a$ 执行若干次区间 $[l,r]$ 加 $1$ 操作，所有操作结束后判定是否存在 $a_i \geq k$，离散化处理显然可行，但这里存在更简单的处理手法。

具体地，从左到右扫描序列，只考虑所有满足 $i = l$ 或 $i = r+1$ 的位置 $i$，因为只有这些位置可能满足 $a_i \neq a_{i-1}$，同时维护当前位置线段覆盖数 $cnt$（最初为 $0$）。如果存在 $x$ 个满足 $i = l$ 的线段和 $y$ 个满足 $i = r+1$ 的线段，就令 $cnt \leftarrow cnt + x - y$，若某一时刻 $cnt \geq k$ 则说明存在合法的 $p$ 作为攻击点。

总体时间复杂度 $O(n \log n \log V)$。

#include<bits/stdc++.h>
using namespace std;
constexpr int inf=1'000'000'000;
int n,k,ans,h[100'005],p[100'005];
long long m;
bool fail(int x){
    map<int,int> w;
    for(int i=1;i<=n;i++) if(h[i]<=x*m){
        int dis=m-(h[i]+x-1)/x;
        ++w[p[i]-dis],--w[p[i]+dis+1];
    }
    int cnt=0;
    for(auto [i,x]:w) if((cnt+=x)>=k) return 0;
    return 1;
}
void solution(){
    cin>>n>>m>>k,ans=-1;
    for(int i=1;i<=n;i++) cin>>h[i];
    for(int i=1;i<=n;i++) cin>>p[i];
    int l=1,r=inf;
    while(l<=r){
        int mid=(l+r)>>1;
        if(fail(mid)) l=mid+1;
        else ans=mid,r=mid-1;
    }
    cout<<ans<<'\n';
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}