一篇题解
# [AGC018B] Sports Festival
# 题面翻译
Takahashi 举办了一场运动会，这场运动会有 个项目，有 个人来参加。
每个人会在所有开展的项目当中，选择她心目中排名最高的那个项目参加。
因此，如果开展全部项目的话，可能某个项目的人数会爆多无比，所以 Takahashi 决定，只开展其中的一部分项目，使得参加人数最多的那个项目，参加人数尽量少。
请输出这个值。
———from@__stdcall
# 分析
首先对于这 个赛事，我们可以一开始都选上，然后我们考虑怎么会让答案变的更优，既然我们要满足最大值最小，那么一个比较显然的想法就是我们每次删去参加人数最多的比赛，然后这个答案一定是不会变的更劣的，因为我们只改动了一个项目，只会发生两种情况
①：对于所有的涉及到改动的人在删掉当前的活动后，如果下一个优先级的活动都一样，那么答案是跟删之前相等的。
②：如果他们的下一个优先级的活动不一样，那么最大值一定是比之前小。
所以这么贪心一定是对的，同时我们对于每个活动删还是不删，一定都是删去的是当前位置之后的位置，那么每个人选择的活动一定是往后走的，然后按照上面的贪心策略删就行了。
#include <cstring> | |
#include <iostream> | |
#include <algorithm> | |
namespace read_write | |
{ | |
template <typename T> | |
inline void read(T &x) | |
{ | |
x = 0; | |
T f = 1; | |
char ch = getchar(); | |
while (ch > '9' || ch < '0') | |
{ | |
if (ch == '-') | |
f = -1; | |
ch = getchar(); | |
} | |
while (ch >= '0' && ch <= '9') | |
x = x * 10 + ch - '0', ch = getchar(); | |
x *= f; | |
return; | |
} | |
template <typename T, typename... Args> | |
inline void read(T &first, Args &...args) | |
{ | |
read(first); | |
read(args...); | |
} | |
template <typename T> | |
inline void write(T x) | |
{ | |
if (x < 0) | |
{ | |
x = -x; | |
putchar('-'); | |
} | |
if (x > 9) | |
write(x / 10); | |
putchar(x % 10 + '0'); | |
} | |
template <typename T> | |
T max(T x, T y) | |
{ | |
return x > y ? x : y; | |
} | |
template <typename T> | |
T min(T x, T y) | |
{ | |
return x > y ? y : x; | |
} | |
template <typename T> | |
void swap(T &a, T &b) | |
{ | |
T tem = b; | |
b = a; | |
a = tem; | |
} | |
} | |
namespace Solve | |
{ | |
using namespace read_write; | |
const int N = 520; | |
int n, m, ans; | |
int a[N][N]; | |
int cnt[N], cur[N]; | |
bool st[N]; | |
void solve() | |
{ | |
read(n, m); | |
for(int i = 1 ; i <= m ; ++ i) // 一开始将所有的活动选上 | |
st[i] = true; | |
for(int i = 1 ; i <= n ; ++ i) | |
{ | |
for(int j = 1 ; j <= m ; ++ j) | |
read(a[i][j]); | |
cur[i] = 1; | |
++ cnt[a[i][1]]; // 记录每个活动参加的人数 | |
} | |
ans = n; | |
for(int k = 1 ; k <= m ; ++ k) | |
{ | |
int mx = -1, pos = 0; | |
for(int i = 1 ; i <= m ; ++ i) // 找到当前的最大值和是哪个活动 | |
if(st[i] && cnt[i] > mx) | |
mx = cnt[i], pos = i; | |
ans = min(ans, mx); // 更新一下答案 | |
st[pos] = false; // 删去这个活动 | |
for(int i = 1 ; i <= n ; ++ i) // 更新有影响的人的选择的活动 | |
{ | |
if(a[i][cur[i]] == pos) | |
{ | |
while(cur[i] < m && !st[a[i][cur[i]]]) | |
++ cur[i]; | |
++ cnt[a[i][cur[i]]]; | |
} | |
} | |
} | |
write(ans); | |
} | |
} | |
int main() | |
{ | |
Solve :: solve(); | |
return 0; | |
} |
