CCPC E Problem Buyer

题目描述

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

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

题解

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

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

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

代码

#include<bits/stdc++.h>

using namespace std;

#define N 100002

typedef 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<node>q;

inline bool cmp(node a,node b){

    if(a.l!=b.l)return a.l<b.l;

    return a.r>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<n&&a[p+1].l<=c[i])p++,q.push(a[p]);

        while(!q.empty()&&q.top().r<c[i])q.pop();

        ans=max(ans,n-(int)q.size()+1);if(q.size())q.pop();

    }

    ++cnt;

    if(ans>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;

}

巴特西

CCPC E Problem Buyer

题目描述

题解

代码

最新文章

热门文章