AtCoder Regular Contest 076 F

题意：

n个人抢m个凳子，第i个人做的位置必须小于li或大于ri，问最少几个人坐不上。

这是一个二分图最大匹配的问题，hall定理可以用来求二分图最大匹配。

关于hall定理及证明，栋爷博客里有：http://blog.csdn.net/werkeytom_ftd/article/details/65658944

可以推出答案为$max\{|x|-Γ(X)\}$，x为左侧点的一个子集，Γ(X)为这些点能到达的右侧点的集合。

证明:

因为二分图有完美匹配的充要条件是对于所有的x都有Γ(X)>=|x|,所以至少要再加$max\{|x|-Γ(X)\}$个点才能让这张图有完美匹配。

考虑向右侧新加$max\{|x|-Γ(X)\}$个点，与左侧所有点都有边，显然对于所有的x都有Γ(X)>=|x|，既这张图有完美匹配。

所以最少加$max\{|x|-Γ(X)\}$个点。

然后就可以枚举Γ(X)，用线段树维护|x|。

#include<bits/stdc++.h>

#define N 200005

#define pd push_back

#define ls x<<1,l,mid

#define rs x<<1|1,mid+1,r

using namespace std;

int n,m;

vector<int>s[N];

int t[N<<2],f[N<<2];

void build(int x,int l,int r)

{

    if(l==r){t[x]=l;return ;}

    int mid=(l+r)>>1;build(ls);build(rs);

    t[x]=max(t[x<<1],t[x<<1|1]);

}

void add(int x,int l,int r,int ll,int rr)

{

    if(l>=ll&&r<=rr)

    {

        t[x]++;f[x]++;return ;

    }

    int mid=(l+r)>>1;

    if(ll<=mid)add(ls,ll,rr);

    if(rr>mid)add(rs,ll,rr);

    t[x]=f[x]+max(t[x<<1],t[x<<1|1]);

}

int qur(int x,int l,int r,int ll,int rr)

{

    if(l>=ll&&r<=rr)return t[x];

    int mid=(l+r)>>1;

    if(ll>mid)return f[x]+qur(rs,ll,rr);

    if(rr<=mid)return f[x]+qur(ls,ll,rr);

    return f[x]+max(qur(ls,ll,rr),qur(rs,ll,rr));

}

int main()

{

    scanf("%d%d",&n,&m);

    int ans=0;

    for(int i=1;i<=n;i++)

    {

        int t1,t2;scanf("%d%d",&t1,&t2);s[t1].pd(t2);

    }

    build(1,0,m+1);

    for(int i=0;i<=m;i++)

    {

        for(auto j:s[i])add(1,0,m+1,0,j);

        ans=max(ans,qur(1,0,m+1,i+1,m+1)-i-m-1);

    }

    printf("%d\n",max(n-m,ans));

    return 0;

}

巴特西

AtCoder Regular Contest 076 F - Exhausted?

最新文章

热门文章