P7391 「TOCO Round 1」自适应 PVZ 题解

· · 题解

P7391 「TOCO Round 1」自适应 PVZ 题解

题目传送门

思路

这道题贪心的方案有点多，这里一一列举。第一，把僵尸出现时刻和走进房子时刻想成左端点和右端点，按照右端点从小到大排序。第二对于同样可以使用的豌豆射手，我们一定选择上次攻击时间最近的豌豆射手攻击僵尸，因为这样可以更灵活的攻击后面的僵尸。

代码

#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;
}