题解-运动会

题目描述

学校将要举行运动会。老师希望聪明的小C对运行项目设置优化。
学校设计了m 项运动，让 n 个同学对这m项运行的喜爱程度进行选择。
每个同学有⼀个 1~m 的排列,表⽰对m 项运动的喜爱排名（从⾼到低）。如 m = 3时，某⼈的排列顺序为3,1,2 ，表⽰他最喜欢项⽬ 3，其次为项⽬1，最后为项⽬2。
小C的任务是要选取⼀些运动,举办这些运动的⽐赛。运动员会参加被举办的运动中,⾃⼰最喜欢的那⼀个运动参加。
你需要选出⼀些运动,使得举办这些运动时,参加⼈数最多的那⼀项 运动参赛⼈数最少,输出这个⼈数。

输入

输⼊有N+1 ⾏。第⼀⾏有两个整数n,m（1<=n,m<=300），表⽰⼈数和待选 的项⽬数量。
接下来n ⾏，每⾏有 m个整数，是1~m 的⼀个排列表⽰每个⼈对 m的项⽬的喜爱排名。

输出

输出只有⼀⾏，包含⼀个整数，即最优⽅案下，参加⼈数最多的那⼀项运动的参赛⼈数。

样例

样例输入

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

样例输出

2

分析

我们可以用贪心和逆向思维来思考这道题。

从m个项目中选出若干个，可以等价为，现在m个项目都已经被选择，需要从中删除若干个。

因此，对于某个局面，我们可以贪心的删除掉选择的人数最多的项目，每次取最小值

简单证明：假设当前局面玩的人数最多的是第k个项目，

如果不删除第k个项目，那么（玩的人数最多的项目玩的人数）将始终大于等于（玩第k个项目的人数），即不可能出现更优解

如果删除第k个项目，那么（玩的人数最多的项目玩的人数）可能会低于（玩第k个项目的人数），也可能会高于（玩第k个项目的人数），即有可能出现更优解

综上所述，对于每种局面，删除掉（玩的人数最多的项目），每次取最小值，即为正确且最优的贪心策略。

所以，我们可以先假设所有的项目都被选择，然后根据贪心策略，不断删除掉选的人数最多的项目，并且取最小值。

代码

#include<bits/stdc++.h>
 
using namespace std;
 
const int N = 300 + 10;
 
int n,m;
int a[N][N];
int cnt[N]; // 统计某个项目被多少人选择
bool st[N]; // 标记某个项目是否被删除掉
int res;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
 
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++)
            cin >> a[i][j];
 	
    res = n;
    
    // 初始局面为所有的项目都被选择
    for(int k = 1;k < m;k++){ // 由于最少需要选择一个项目举行，所以最多删除 m-1 次
        for(int i = 1;i <= n;i++) cnt[i] = 0; // 对于每个局面，初始化
         
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= m;j++)
                if(!st[a[i][j]]){
                    // 因为对1~m的喜欢程度是递减的，所以第一个没被删除的项目即为目前所有项目中最喜欢的
                    cnt[a[i][j]]++;
                    break;
                }
 
        int tmp = 1,pos = 0; // tmp指选的人数最多的项目选的人数，pos指选的人数最多的项目的编号
        for(int i = 1;i <= m;i++)
            if(!st[i] && tmp < cnt[i]){
                tmp = cnt[i];
                pos = i;
            }
 
        res = min(res,tmp); // 每次取最小值
 
        st[pos] = true; // 将选的人数最多的项目删去
    }
 
    cout << res;
 
    return 0;
}