python/TangDou/JiShuanKe/2023-03-16/T3707.cpp

#include <bits/stdc++.h>

using namespace std;
int n;
const int N = 2e5 + 10;
int a[N];

int ans; // 组数
int cnt; // 当前组内人数

/*
Q:最多能组织多少个足球队?
A:举栗子说明：
3
1 2 2

① 将能力值从小到大排序，能力值为: 1 2 2

② 第1个小朋友，能力值a[1]=1,可以独立成班,创建新班级ans++,此时ans=1,表示1个班级已成班

③ 第2个小朋友，能力值a[1]=2,他要求2个人成班，他自己是1个，还要求再加入1个，
也就是下一个人也需要加入他们的班级，本轮没有班级成班成功

④ 第3个小朋友，能力值a[2]=2,继续加入到上个班中,在他加入后，此班的班额满足了第3个小朋友的要求,此班成班成功

总结:
（1）因为数据范围是2e5,所以O(N^2)的肯定要挂，O(NlogN)的也可能会挂，只能考虑O(N)或 O(logN)的算法
（2）贪心：考虑在现有规则下，什么样的学生应该留下来，什么样的学生应该抛弃掉？
肯定是要求低的留下来，要求高的扔掉。此处的要求就是：能力低，成班额度低。
也就是谁能力差谁留下，谁能力高谁不要。（这是什么鬼要求！！）
引导我们按能力值由小到大排序。
(3) 捋着由小到大的能力值，能成班的就让它们成班，实在成不了班，就放弃。
*/

int main() {
    freopen("T3707.in", "r", stdin);
    // freopen("T3707.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    // 由小到大排序
    sort(a + 1, a + 1 + n);

    for (int i = 1; i <= n; i++) {
        cnt++;                           // 当前组人数+1
        if (cnt >= a[i]) ans++, cnt = 0; // 成功完成一个成班，清空下一组人数为0
    }
    cout << ans << endl;
    return 0;
}