【问题描述】

小 F 和大 F 开了一所幼儿园，春天到了，幼儿园要举办一场运动会！
幼儿园里有 N 个小朋友，运动会里有 M 个项目可供选择，每个小朋友都对 M 个项目有一定的喜好程度。对于第 i 个小朋友，他第 j 喜欢的项目是 aij。并且保证对于每个小朋友，他都不会有两个一样喜欢的项目。
幼儿园的园长小 F 和副园长大 F 对运动会的事情头疼不已，她们希望玩的人数最多的项目玩的人数最少，否则她们在最受欢迎的项目举行时会忙不过来。她们希望从 M 个项目中选出若干个项目在运动会中举行（可以全选，但不能一个也不选），每个小朋友会且仅会玩一个项目，并且他玩的项目一定是举行的项目中他最喜欢的。
很不幸，今天幼儿园停电了，电脑不能用，小 F 和大 F 决定将这个问题交给聪明的你，请你求出玩的人数最多的项目玩的人数的最小值。

【输入】

第 1 行两个整数 N 和 M，表示小朋友的个数和备选运动项目的个数。
第 2 至 N+1 行，每行 M 个整数。第 i+1 行的第 j 个整数表示 aij，表示第 i 个小朋友第 j 喜欢的项目。保证 ai1..aiM 是 1..M 的一个排列。

【输出】

一个整数，表示玩的人数最多的项目玩的人数的最小值。

【样例 1】

4 5
5 1 3 4 2
2 5 3 1 4
2 3 1 4 5
2 5 4 3 1

2

【样例 1 解释】

一种最优方案是选择举行 1,3,4 三个项目，这样的话，4 个小朋友玩的项目分别是1,3,3,4，玩的人数最多的项目是 3,有 2 个人玩，所以答案是 2。

【样例 2】

3 3
2 1 3
2 1 3
2 1 3

3

【样例 2 解释】

由于无论怎么选择举行的项目，3 个小朋友玩的项目都是同一个，所以答案一定是 3。

【数据范围】

对于 30%的数据，M<=16。
对于另外 30%的数据，N<=3。
对于 100%的数据，1 <= N,M <= 200。

思路

由于需要删去一些项目,所以先假设全选,然后一项项删除,每次必须删除当前人数最多的项目,不然最多的永远是它且不会减少,每次统计答案即可

代码

#include <bits/stdc++.h>
using namespace std;

int n,m,a[305][305],cnt[305],used[305],ans=1e9;

int get(int l){
    for (int i=1;i<=m;++i){
        if (used[a[l][i]]) continue;
        return a[l][i];
    }
    return -1;
}

int main(){
    cin>>n>>m;
    for (int i=1;i<=n;++i){
        for (int j=1;j<=m;++j){
            scanf("%d",&a[i][j]);
        }
    }
    for (int i=1;i<=m;++i){
        memset(cnt,0,sizeof(cnt));
        for (int j=1;j<=n;++j){
            cnt[get(j)]++;
        }
        int Tans=0,id=0;
        for (int j=1;j<=m;++j){
            if (Tans<cnt[j]){
                Tans=cnt[j];
                id=j;
            }
        }
        ans=min(ans,Tans);
        used[id]=1;
    }
    cout<<ans<<endl;
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/48/