思路

算法是二分和贪心。

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

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

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

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

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

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

代码如下：

CPP

#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

完结撒花。

题解：P12015 [NOISG 2025 Finals] 怪物

文章操作

思路

相关推荐

评论

题解：P12015 [NOISG 2025 Finals] 怪物