「AtCoder Grand018B」Sports Festival(暴力)

题目链接B - Sports Festival

题意

n(1~300)个人m(1~300)个活动,(A_{ij})表示i第j喜欢的活动,每个人选择在举办的活动里最喜欢的,因此可以通过选择一些活动来举办,使得最多人参加的活动的参加人数最少,求这个最小值。

题解

每次找到最多人参加的活动,置为不举办的,然后再遍历一遍找到最多人参加的活动。。。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define N 301
int n,m;
int a[N][N];
int num[N];
bool v[N];
int ans;
int main(){
	scanf("%d%d",&n,&m);
	int s;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j)
			scanf("%d",&a[i][j]);
		int b=a[i][1];
		if(++num[b]>ans){
			ans=num[b];
			s=b;
		}
	}
	for(int i=1;i<m;++i){
		memset(num,0,sizeof num);
		v[s]=1;
		int tans=0;
		for(int j=1;j<=n;++j){
			for(int k=1;k<=m;++k){
				int b=a[j][k];
				if(!v[b]){
					if(++num[b]>tans){
						tans=num[b];
						s=b;
					}
					break;
				}
			}
		}
		ans=min(ans,tans);
	}
	printf("%d",ans);
	return 0;
}
原文地址:https://www.cnblogs.com/flipped/p/7226605.html