官方题解

cookiebus 2024-04-19 9:41:12 7 返回题目

第一,把僵尸出现时刻和走进房子时刻想成左端点和右端点,按照右端点从小到大排序。

第二对于同样可以使用的豌豆射手,我们一定选择上次攻击时间最近的豌豆射手攻击僵尸,因为这样可以更灵活的攻击后面的僵尸。

参考代码:

#include<bits/stdc++.h>
using namespace std;
int n,m,i,j,ans;
multiset<int>s;//multiset维护上次攻击时间最近的豌豆射手
struct zombie{
	int l,r;
}z[200001];
bool cmp(zombie x,zombie y){
	return x.r<y.r;
}
int main(){
	multiset<int>::iterator it;
	scanf("%d%d",&n,&m);
	if(m>=n){
		printf("0");
		return 0;
	}
	for(i=1;i<=n;i++)
		scanf("%d%d",&z[i].l,&z[i].r);
	sort(z+1,z+1+n,cmp);
	for(i=1;i<=n;i++){
		it=s.upper_bound(z[i].l);
		if(it!=s.begin()){
			it--;
			s.erase(it);
			s.insert(z[i].r);
		}
		else{
			if(s.size()+1>m)//打不死的情况
				ans++;
			else
				s.insert(z[i].r);	
		}
	}
	printf("%d",ans);
	return 0;
}
{{ vote && vote.total.up }}