AGC 018 B Sports Festival - 贪心

题目大意：N个人M个项目，每个人都有自己关于M个项目的喜好程度的排列。现在选出M个活动的一个非空子集，每个人会参加子集中自己最喜欢的那个，要求参加人数最多的活动的人数最少。$n,m\le 300$n,m≤300
题解：二分答案x，考虑贪心，那些被超过x人作为最喜欢的项目要删去，然后又出现了新的这样的项目继续被删除，以此类推，直到不存在这样的项目，或者一个人无项目可选为止。

#include<bits/stdc++.h>
#define gc getchar()
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define Rep(i,v) rep(i,0,(int)v.size()-1)
#define clr(a,n) memset(a,0,sizeof(int)*(n+1))
#define lint long long
#define db double
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define debug(x) cerr<<#x<<"="<<x
#define sp <<" "
#define ln <<endl
using namespace std;
typedef pair<int,int> pii;
typedef set<int>::iterator sit;
inline int inn()
{
    int x,ch;while((ch=gc)<"0"||ch>"9");
    x=ch^"0";while((ch=gc)>="0"&&ch<="9")
        x=(x<<1)+(x<<3)+(ch^"0");return x;
}
const int N=310;queue<int> q;
int cnt[N],del[N],c[N][N],fp[N],a[N][N],b[N][N];
int check(int x,int n,int m)
{
    clr(cnt,m),clr(del,m);
    rep(i,1,n) clr(c[i],m),cnt[a[i][fp[i]=1]]++;
    while(!q.empty()) q.pop();
    rep(i,1,m) if(cnt[i]>x) q.push(i),del[i]=1;
    while(!q.empty())
    {
        int z=q.front();q.pop();
        rep(i,1,n) c[i][b[i][z]]=1;
        rep(i,1,n)
        {
            int t=0;
            while(fp[i]<=m&&c[i][fp[i]]) fp[i]++,t=1;
            if(fp[i]>m) return false;
            int y=a[i][fp[i]];if(t) cnt[y]++;
            if(cnt[y]>x&&!del[y]) q.push(y),del[y]=1;
        }
    }
    return true;
}
int main()
{
    int n=inn(),m=inn(),L=1,R=n,mid=(L+R)>>1;
    rep(i,1,n) rep(j,1,m) a[i][j]=inn(),b[i][a[i][j]]=j;
    while(L<=R)
    {
        if(check(mid,n,m)) R=mid-1;
        else L=mid+1;mid=(L+R)>>1;
    }
    return !printf("%d
",L);
}