题解：CF2037F Ardent Flames

zhouruoheng · 2024-11-19 17:22:09 · 题解

二分答案，设攻击了 k 次。

因为只能是在同一个位置 p 攻击，所以第 i 个敌人每次攻击需要受到至少 t_i=\lceil\frac{h_i}{k}\rceil 的伤害，因此 p 的范围就是 [x_i-(m-t[i]),x_i+(m-t[i])]，若 m < t_i 则一定无法击败第 i 个敌人。

这样就转化成了 n 个区间的覆盖问题，问是否有一个点被覆盖了至少 k 次。

离散化加差分轻松搞定，复杂度为 O(n\log(n)\log(V))。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=2e5+5,inf=1e9;
int n,m,k;
int h[N],x[N],t[N];
int tot;
int b[N],c[N];
bool check(int k)
{
    tot=0;
    for(int i=1;i<=n;i++) 
    {
        t[i]=(h[i]+k-1)/k;
        if(t[i]<=m) 
        {
            c[++tot]=x[i]-(m-t[i]);
            c[++tot]=x[i]+(m-t[i])+1;
        }
    }
    sort(c+1,c+tot+1);
    tot=unique(c+1,c+tot+1)-c-1;
    for(int i=1;i<=tot;i++) b[i]=0;
    for(int i=1;i<=n;i++)
    {
        if(t[i]<=m)
        {
            int l=lower_bound(c+1,c+tot+1,x[i]-(m-t[i]))-c;
            int r=lower_bound(c+1,c+tot+1,x[i]+(m-t[i])+1)-c;
            b[l]++,b[r]--;
        }
    }
    for(int i=1;i<=tot;i++) b[i]+=b[i-1];
    for(int i=1;i<=tot;i++) if(b[i]>=k) return 1;
    return 0;
}
void solve()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) cin>>h[i];
    for(int i=1;i<=n;i++) cin>>x[i];
    int l=1,r=inf,mid,ans=-1;    
    while(l<=r)
    {
        mid=l+r>>1;
        if(check(mid)) r=mid-1,ans=mid;
        else l=mid+1;
    }
    cout<<ans<<'\n';
}
int main ()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}