题解：AT_abc214_e [ABC214E] Packing Under Range Regulations

· · 题解

问题陈述

给你一些球以及它们应该在的区间，每个点只能放一个球，问能否放完。（多测）

思路

这题首先想到贪心：合理放法，放左边比放右边更好，因为这样可以给后面的留下更多位置。

但一个一个遍历肯定超时。

所以我们需要一个数据结构来维护，它需要满足以下特点：

这就是堆！

用堆维护右端点最小值即可，详情见代码。

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
struct node{
    int l;
    int r;
}a[200010];
bool cmp(node t1,node t2){return t1.l<t2.l;}
priority_queue<int,vector<int>,greater<int>> h;
int t,n,al,now;
bool flag;
int main(){
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--){
        flag=false;//标记
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i].l>>a[i].r;
        sort(a+1,a+1+n,cmp);//按左端点升序排序，贪心
        al=0,now=0;//L
        while(h.size()) h.pop();////多测不清空，亲人两行泪
        while(now<n){//遍历
            if(h.empty()){//如果是空的就压进来，不然就是空的，无法进行之后的操作。
                al=a[++now].l;
                h.push(a[now].r);
            }
            while(now<n&&a[now+1].l<=al){//如果下一个在al之前，那无需更新，直接加入即可，但是最后可能将al遍历了，所以要+1
                h.push(a[++now].r);
            }
            if(h.top()<al){/如果当前右端点小于左端点，无解
                cout<<"No"<<endl;
                flag=true;
                break;
            }
            al++;
            h.pop();
        }
        if(flag==true) continue;
        while(!h.empty()){////如果里面还有没被处理的区间，那就按之前的方法处理即可。
            if(h.top()<al){
                cout<<"No"<<endl;
                flag=true;
                break;
            }
            al++;
            h.pop();//当前的处理完了，pop掉，不然可能干扰后续操作
        }
        if(flag==false) cout<<"Yes"<<endl;
    }
    return 0;
}