分组的最大数量

记住这句:只要人数 1,2,3,... 严格递增,总成绩自动跟着递增,答案就是最大的 k 使 1+2+...+k ≤ n。下面分三段演给你看。

先看原始的 6 个成绩,乱序排着。直接盯着成绩去凑「总成绩递增」很难,我们换个角度:先把成绩从小到大排好。

升序排好后是 [3,5,6,7,10,12]。接下来从左往右切:第 1 组拿 1 个人,第 2 组拿 2 个人,第 3 组拿 3 个人,人数严格递增。看看总成绩会不会自动跟着涨。

第 1 组从左边接着拿 1 个人,拿到的是 [3]。蓝色是前面已经分好的组。

第 1 组总成绩 3。它是第一组,先记着,和下一组比。

第 2 组从左边接着拿 2 个人,拿到的是 [5, 6]。蓝色是前面已经分好的组。

第 2 组总成绩 11,比上一组的 3 大。注意我们根本没刻意去凑,只因为这组人更多、每个人成绩都不小于上一组,总和自然更高。

第 3 组从左边接着拿 3 个人,拿到的是 [7, 10, 12]。蓝色是前面已经分好的组。

第 3 组总成绩 29,比上一组的 11 大。注意我们根本没刻意去凑,只因为这组人更多、每个人成绩都不小于上一组,总和自然更高。

三组都切好了:人数 1、2、3 严格递增,总成绩 3、11、29 也严格递增,两个条件全满足。可见「总成绩」这条根本没拦住我们,真正的瓶颈只是「人数够不够凑出严格递增」。

既然只跟人数有关,干脆把成绩全扔掉。这排格子代表候选组数 k,从 1 开始逐个试:分 k 组至少要 1+2+...+k 个人,记成 T(k)。只要 T(k) 不超过总人数 6,这个 k 就可行。

试 k = 1:至少要 1 = 1 个人。不超过 6,可行,标绿。继续看更大的 k。

试 k = 2:至少要 1+2 = 3 个人。不超过 6,可行,标绿。继续看更大的 k。

试 k = 3:至少要 1+2+3 = 6 个人。正好等于 6,人刚好用完,仍然可行,标绿。继续看更大的 k。

试 k = 4:至少要 1+2+3+4 = 10 个人,已经超过 6 了,凑不出来,标红。既然 T(k) 只增不减,再大的 k 更不可能,到此为止。最后一个绿色的 k = 3 就是答案。

逐个试当然行,但 n 能到十万,得用二分。把条件 k(k+1)/2 ≤ n 两边乘 2,写成 k²+k ≤ 2n,这里 2n = 12。在 0 到 6 之间二分,找最大的满足它的 k。

区间 [0, 6],中点向上取整 mid = 3。算 3²+3 = 12,和 12 比:不超过,说明分 3 组可行,这个 mid 本身可以成为答案。

因为可行,把下界 l 拉到 3,绿色候选也跟着到 3。答案至少 3,还想更大,所以去 mid 右边接着找。

区间 [3, 6],中点向上取整 mid = 5。算 5²+5 = 30,和 12 比:超过了,分 5 组人不够,mid 及它右边都不行。

因为不可行,把上界 r 压到 mid - 1 = 4,mid 和它右边整段排除。区间越缩越小。

区间 [3, 4],中点向上取整 mid = 4。算 4²+4 = 20,和 12 比:超过了,分 4 组人不够,mid 及它右边都不行。

因为不可行,把上界 r 压到 mid - 1 = 3,mid 和它右边整段排除。区间越缩越小。

l 和 r 碰头都停在 3,二分结束。绿色格 3 就是最大能分的组数,答案 = 3,和前面一块一块切出来的 3 组完全对上。

边界都在三角数上卡:1 人 1 组、2 人 1 组、3 人 2 组、10 人 4 组,记住 T(k)=k(k+1)/2 逐个套即可。

抓住两点:总成绩条件靠升序切块自动满足;组数就是让 k(k+1)/2 ≤ n 的最大 k。