分组的最大数量 图解题解

分组要同时满足人数和总成绩递增，求的是什么

把学生按成绩分成有序几组，要求后一组人数比前一组多、后一组总成绩也更高，返回最多能分几组。人数除不尽也不碍事：多出的学生并进最后一组即可——只要求人数严格递增，末组更大不违规。题面 grades=[10,6,12,7,3,5] 有 6 个人，答案是 3（人数 1、2、3 三组）；换成 grades=[8,8] 只两人，硬分两组人数就相等，最多 1 组。

为什么『后一组总成绩更高』这条根本不用管

先把成绩从小到大排好，再从左往右一块块切给各组：第一组拿最小的几个，第二组往后拿更多。后一组人数更多，且每人成绩都不小于前一组任何人——人更多、每个还不更小，总成绩必然更大。所以人数一严格递增，总成绩就自动跟着递增，成绩的具体数值不影响答案，干脆全扔掉、只盯人数。

问题缩成：最大的 k 使 k(k+1)/2 ≤ n

人数要严格递增，分成 k 组最省人的排法就是 1、2、3、…、k 一路加一，共要 k(k+1)/2 个人（三角数）。只要它不超过 n 就一定分得出来。所以能否分成 k 组等价于 k(k+1)/2 ≤ n，答案就是让它成立的最大 k。题面 n 是 6 时 1+2+3=6 恰好用完可分 3 组；再加一组要 10 个人就凑不齐。

逐个试 k 太慢，怎么换成二分

n 能到十万，从 k 取 1 逐个往上试，最坏试到答案那档，白扫一截。好在 k(k+1)/2 随 k 单调变大，所有 k 被切成两半：小的都 ≤ n、大的都超 n，答案正是分界上最后一个满足的 k。这种不套公式、而是猜一个 k 用 k(k+1)/2 ≤ n 验一验再往一边收的思路，就是二分答案（二分的是答案本身，不是下标）。参考代码两边乘 2 成 k²+k ≤ 2n，bisect_right 在 range(n+1) 上按 key x²+x 找第一个超过 2n 的位置，减 1 即最大可行 k。下面演算用手写 l、r 二分展开，bisect_right 就是它的库函数封装。

题面 6 个人这组，二分三轮各砍向哪半

总人数 6，两倍即 2n=12，在 0 到 6 间找最大的 k 使 k²+k ≤ 12。左界 l 起于 0、右界 r 起于 6。第一轮中点向上取整取 3，3²+3=12 不超 12，分 3 组可行、这个中点可能就是答案，把 l 拉到 3。第二轮 [3,6] 中点取 5，5²+5=30 超 12，分 5 组人不够，r 退到 4。第三轮 [3,4] 中点取 4，4²+4=20 仍超 12，r 压到 3。此时 l、r 都停在 3，二分结束，答案 3，正是前面切出的三组。

等号一丢、中点取整一错，答案就少一组

别真在成绩上凑总成绩——切块后它自动成立。等号也别丢：n 是 6 时 T(3) 正好等于 6，人刚好用完仍可行，写成严格小于会把这组判没、答案少一组。手写二分还藏个暗坑：找『最大可行』时中点要向上取整、配 l=mid 与 r=mid−1；若向下取整，区间剩两格时中点永远卡左端、l 推不动，就死循环。复杂度上，答案只由人数 n 定、不遍历成绩数组，时间 O(log n)、空间 O(1)。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def maximumGroups(self, grades: List[int]) -> int:
        n = len(grades)
        return bisect_right(range(n + 1), n * 2, key=lambda x: x * x + x) - 1

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int maximumGroups(vector<int>& grades) {
        int n = grades.size();
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (1LL * mid * mid + mid > n * 2LL) {
                r = mid - 1;
            } else {
                l = mid;
            }
        }
        return l;
    }
};

Java

import java.util.*;
class Solution {
    public int maximumGroups(int[] grades) {
        int n = grades.length;
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (1L * mid * mid + mid > n * 2L) {
                r = mid - 1;
            } else {
                l = mid;
            }
        }
        return l;
    }
}