题目描述

有一些区间，还有一些点。

问最小的k使得选出任意k个区间，每个点都可以匹配上区间，一个区间只能匹配一次。

题解

考虑对于每一个点，我们有\(x\)个区间包含它，那么答案的一个下界是\(n-x+1\)。

但是这样没有考虑到一个区间被两个点匹配的情况。

那么我们从左到右做，没到一个点，就把右端点最靠左的合法区间删掉，可以证明这也是下界且可以达到。

代码

#include
    
     using namespace std;#define N 100002typedef long long ll;int c[N],n,m;int cnt;inline ll rd(){    ll x=0;char c=getchar();bool f=0;    while(!isdigit(c)){if(c=='-')f=1;c=getchar();}    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}    return f?-x:x;}struct node{    int l,r;    inline bool operator <(const node &b)const{        return r>b.r;    }}a[N];priority_queue
     
      q;inline bool cmp(node a,node b){    if(a.l!=b.l)return a.l
      
       b.r; }inline void solve(){    while(!q.empty())q.pop();    n=rd();m=rd();    for(int i=1;i<=n;++i){        a[i].l=rd();a[i].r=rd();    }    for(int i=1;i<=m;++i)c[i]=rd();    sort(c+1,c+m+1);    sort(a+1,a+n+1,cmp);    int p=0;    int ans=0;    for(int i=1;i<=m;++i){        while(p
       
        <=c[i])p++,q.push(a[p]);        while(!q.empty()&&q.top().r
        
         n)printf("Case #%d: IMPOSSIBLE!\n",cnt);    else printf("Case #%d: %d\n",cnt,ans);}int main(){    int T=rd();    while(T--)solve();    return 0;}