题解：P12015 [NOISG 2025 Finals] 怪物

wang6w6 · 2025-05-18 20:50:08 · 题解

题目传送门

思路

算法是二分和贪心。

先把怪物和地雷坐标排序。

我们先分情况讨论如何打死怪物，由题意知可分为两种，即直接减生命值，用地雷炸死。

第一种，显然，如果怪物自身生命值小于或等于距离怪物最近的地雷的距离，就直接减去。

第二种，我们可以再分为两种情况，即距离左右两端地雷的距离不等或相等，前者可以看距离哪个短就走到哪个地雷再标记一下，而后者如果左边的地雷被标记了就优先到左边的，否则就到右边的并标记，这样可以利用之前被标记的地雷，减少花费。

其中的左右距离相等很难想到，要细心。

至于二分，我们可以使用 upper_bound 函数，它可以在已排序的范围内查找第一个大于给定值的元素，以便于我们找到怪兽左右边的地雷的坐标。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+5;
ll n,k,x[N],l,r,lx,rx,ans,cnt,vis[N];
struct stu{
    ll a,h;//要注意a是坐标，h是生命值！！！ 
}d[N];
bool cmp(stu a,stu b){
    return a.a<b.a;
}
int main(){
    cin>>n>>k;
    for(ll i=1;i<=n;i++){
        cin>>d[i].a>>d[i].h;
    }
    for(ll i=1;i<=k;i++){
        cin>>x[i];
    }
    sort(d+1,d+1+n,cmp);//排序 
    sort(x+1,x+1+k);
    for(ll i=1;i<=n;i++){
        r=upper_bound(x+1,x+1+k,d[i].a)-x;//在已排序的范围内查找第一个大于给定值的元素
        l=r-1;//左右地雷的坐标 
        lx=d[i].a-x[l];
        rx=x[r]-d[i].a;//距离左右地雷的距离
        if(x[l]<=0) lx=1e18;//防止越界 
        if(x[r]<=0) rx=1e18;
        if(min(rx,lx)>=d[i].h){//第一种情况 
            ans+=d[i].h;
        }else if(rx!=lx){//第二种情况 
            if(rx>=lx){
                ans+=lx;
                vis[l]=1;
            }else{
                ans+=rx;
                vis[r]=1;
            }
        }else{//左右相等 
            if(vis[l]==1){
                ans+=lx;
            }else{
                ans+=rx;
                vis[r]=1;
            }
        }
//      cout<<lx<<" "<<rx<<' '<<ans<<"\n";
    }
    for(ll i=1;i<=k;i++){
        ans+=vis[i];//引爆被标记的的地雷 
    }
    cout<<ans;
    return 0;
}
//1 2 3 4 5
//      *
//  2   5 4

完结撒花。