#include 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; }