You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
64 lines
2.0 KiB
64 lines
2.0 KiB
2 years ago
|
# 足球小队
|
||
|
|
|
||
|
|
### 题目描述
|
||
|
|
蒜老师为了提高同学们的身体素质，想要在班里组织若干个足球队。（每个足球队的人数有可能不同。）
|
||
|
|
|
||
|
|
第 $i$ 同学有一个训练值 $a_i$，对于这个同学想要加入的足球队来说，这个足球队的人数一定要**大于等于** $a_i$。
|
||
|
|
|
||
|
|
不一定每个人都要加入足球队，问蒜老师**最多**能组织多少个足球队。
|
||
|
|
|
||
|
|
### 输入格式
|
||
|
|
|
||
|
|
输入共两行。
|
||
|
|
|
||
|
|
第一行输入一个正整数 $n$，表示班里有多少同学。
|
||
|
|
|
||
|
|
第二行输入 $n$ 个以空格隔开的正整数 $a_i$，第 $i$ 个数表示第 $i$ 个同学的训练值。
|
||
|
|
|
||
|
|
### 输出格式
|
||
|
|
|
||
|
|
输出共一个整数，表示蒜老师最多能组织多少个足球队。
|
||
|
|
|
||
|
|
### 数据范围
|
||
|
|
|
||
|
|
对于 $10\%$ 的数据，有 $1\leq n\leq 10^3$，且每个同学的训练值 $a_i=1$。
|
||
|
|
|
||
|
|
对于另外 $20\%$ 的数据，有 $1\leq n\leq 10^3$，且每个同学的训练值 $a_i$ 等于 $1$ 或等于 $2$。
|
||
|
|
|
||
|
|
对于另外 $100\%$ 的数据，有 $1\leq n\leq 2\times 10^5,1\leq a_i\leq n$。
|
||
|
|
|
||
|
|
<div style="page-break-after: always"></div>
|
||
|
|
|
||
|
|
### 题解
|
||
|
|
对于一个满足条件的队伍：队伍人数 $cnt$ 要大于等于**该队伍**中所有人的 $a_j$ 值，即 $cnt \geq \max\{a_j\}$，满足第 $j$ 个人在该队伍中。
|
||
|
|
|
||
|
|
可以考虑贪心求解，因为对于人数要大于等于队伍中所有人 $a_i$ 的最大值，所以将 $a_i$ 从小到大排序，然后再按照顺序将人加入到队伍中，满足条件后，维护下一个队伍。
|
||
|
|
|
||
|
|
#### 参考代码
|
||
|
|
|
||
|
|
```c++{.line-numbers}
|
||
|
|
#include <bits/stdc++.h>
|
||
|
|
using namespace std;
|
||
|
|
const int maxn = 200010;
|
||
|
|
int n, a[maxn];
|
||
|
|
int main() {
|
||
|
|
cin >> n;
|
||
|
|
for (int i = 1; i <= n; i++) {
|
||
|
|
cin >> a[i];
|
||
|
|
}
|
||
|
|
sort(a + 1, a + n + 1);
|
||
|
|
int ans = 0, cnt = 0;
|
||
|
|
for (int i = 1; i <= n; i++) {
|
||
|
|
cnt++;
|
||
|
|
if (cnt >= a[i]) {
|
||
|
|
ans++;
|
||
|
|
cnt = 0;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
cout << ans << endl;
|
||
|
|
return 0;
|
||
|
|
}
|
||
|
|
```
|
||
|
|
|
||
|
|
<div style="page-break-after: always"></div>
|