题目重述 有 n n 个小朋友，第 i i 个小朋友要求所在队伍人数 至少 为 a i a i ​ （包括自己）。

目标：

最大化队伍数量

在队伍数最多的前提下，最小化人数最多的队伍的人数

关键观察 如果一个小朋友的 a i

x a i ​ =x，那么他所在的队伍人数必须 ≥ x ≥x。

为了 最大化队伍数量，我们希望每个队伍人数尽量少。

但是每个队伍的人数必须满足队伍里 要求最高 的那个小朋友。

思路推导

1. 排序的必要性 假设队伍里要求最高的小朋友是 a max ⁡ a max ​ ，那么该队伍人数必须 ≥ a max ⁡ ≥a max ​ 。

如果我们把要求高的小朋友和要求低的小朋友混在一起，可能造成人数浪费，从而减少队伍总数。

结论：应该把要求相近的小朋友放在一起，避免大要求小朋友“浪费”队伍容量。

2. 为什么从大到小排序 假设我们按 a i a i ​ 从大到小 排序：

第一个小朋友 a 1 a 1 ​ 最大，需要队伍人数 ≥ a 1 ≥a 1 ​

我们直接取前 a 1 a 1 ​ 个小朋友组成一队，这样第一个小朋友的要求被满足

这 a 1 a 1 ​ 个小朋友里，其他人的 a i ≤ a 1 a i ​ ≤a 1 ​ ，所以他们的要求也被满足（因为队伍人数 = a 1 ≥ a i a 1 ​ ≥a i ​ ）

接着从第 a 1 + 1 a 1 ​ +1 个小朋友继续同样操作。

3. 正确性证明 为什么这样最大化队伍数？

每个队伍人数 = 该队伍第一个小朋友的 a i a i ​ ，这是满足他要求的 最小人数

如果某个队伍人数 > 需要的最大值，那么多出来的人可以分出去组成新队伍，从而增加队伍总数

因此，让每个队伍人数刚好等于最大要求，是队伍数最多的方案

为什么这样最小化最大队伍人数？

在队伍数最多的前提下，每个队伍人数已经最小化（等于最大要求）

所以最大队伍人数 = 所有小朋友中最大的 a i a i ​ ，这是理论最小值

算法步骤 输入： n n 和 a 1 , a 2 , … , a n a 1 ​ ,a 2 ​ ,…,a n ​

处理：

将小朋友按 a i a i ​ 从大到小排序，记住原始编号

初始化队伍列表

设置指针 i

0 i=0

循环直到 i ≥ n i≥n：

取当前小朋友的要求 n e e d

a i need=a i ​

新建队伍，从 i i 开始取 n e e d need 个小朋友加入该队伍

i i 增加 n e e d need

输出：

队伍数量 t t

每行：队伍人数 + 小朋友编号（原始编号）

示例演示 输入：

text 5 2 1 2 2 3 步骤：

原始数据：

(a₁=2, id=1), (a₂=1, id=2), (a₃=2, id=3), (a₄=2, id=4), (a₅=3, id=5)

按 a i a i ​ 从大到小排序：

(3,5), (2,1), (2,3), (2,4), (1,2)

分组：

第一队：第一个小朋友要求 3 → 取前 3 人：id=[5,1,3]，队伍人数=3

第二队：接着从第4个开始，要求 2 → 取2人：id=[4,2]，队伍人数=2

输出：

text 2 3 5 1 3 2 4 2 复杂度分析 时间复杂度： O ( n log ⁡ n ) O(nlogn)，主要是排序

空间复杂度： O ( n ) O(n)，存储排序结果和队伍信息

总结 这道题的核心贪心策略是：

按要求从大到小排序

每个队伍人数 = 该队伍第一个小朋友的要求

连续取人组队

这样能在满足所有要求的前提下，最大化队伍数量，同时最小化最大队伍人数。