题目链接:https://agc018.contest.atcoder.jp/tasks/agc018_b
题目:
题目大意:
有N个人参加M个体育项目,每个人对体育项目的喜爱程度有一个排名,A[i][j]表示第i个人第j喜欢的体育项目,每个人会参加存在的体育项目中他最喜欢的。现在我们需要选出一些体育项目,使得参加人数最多的体育项目参加的人数最少化
题解:
先将所有的体育项目选上,找出参加人数最多的项目
假设去掉的体育项目中不包括这个项目,参加人数最多的项目拥有的人数一定不变
那么考虑我们每次把参加人数最多的项目删掉,再计算现在参加人数最多的项目,在整个过程中取ans=min(ans,当前参加人数最多的项目拥有的人数)
时间复杂度$O(NM^2$)
AC代码如下:
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cstdio>
using namespace std;const int N=+;
const int inf=1e9+;
int n,m,ans;
int a[N][N],vis[N],num[N];
inline int read()
{
char ch=getchar();
int s=,f=;
while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}
return s*f;
}
int main()
{
n=read();m=read();
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
a[i][j]=read();
ans=inf;
for (int i=;i<=m;i++)
{
memset(num,,sizeof(num));
for (int j=;j<=n;j++)
for (int k=;k<=m;k++)
if (!vis[a[j][k]])
{
num[a[j][k]]++;
break;
}
int s,tans=;
for (int j=;j<=m;j++)
{
if (tans<num[j])
{
s=j;
tans=num[j];
}
}
vis[s]=;
ans=min(ans,tans);
}
printf("%d\n",ans);
return ;
}