分组的最大数量 图解题解

这道题到底在问什么

输入

grades = [10,6,12,7,3,5]

输出

3　（人数 1,2,3 三组）

输入

grades = [8,8]

输出

1　（分两组人数就会相等，不行）

最优解：一步一步想明白

1. 3记住这句:只要人数 1,2,3,... 严格递增,总成绩自动跟着递增,答案就是最大的 k 使 1+2+...+k ≤ n。下面分三段演给你看。
2. 4先看原始的 6 个成绩,乱序排着。直接盯着成绩去凑「总成绩递增」很难,我们换个角度:先把成绩从小到大排好。
3. 5升序排好后是 [3,5,6,7,10,12]。接下来从左往右切:第 1 组拿 1 个人,第 2 组拿 2 个人,第 3 组拿 3 个人,人数严格递增。看看总成绩会不会自动跟着涨。
4. 6第 1 组从左边接着拿 1 个人,拿到的是 [3]。蓝色是前面已经分好的组。
5. 7第 1 组总成绩 3。它是第一组,先记着,和下一组比。
6. 8第 2 组从左边接着拿 2 个人,拿到的是 [5, 6]。蓝色是前面已经分好的组。
7. 9第 2 组总成绩 11,比上一组的 3 大。注意我们根本没刻意去凑,只因为这组人更多、每个人成绩都不小于上一组,总和自然更高。
8. 10第 3 组从左边接着拿 3 个人,拿到的是 [7, 10, 12]。蓝色是前面已经分好的组。
9. 11第 3 组总成绩 29,比上一组的 11 大。注意我们根本没刻意去凑,只因为这组人更多、每个人成绩都不小于上一组,总和自然更高。
10. 12三组都切好了:人数 1、2、3 严格递增,总成绩 3、11、29 也严格递增,两个条件全满足。可见「总成绩」这条根本没拦住我们,真正的瓶颈只是「人数够不够凑出严格递增」。
11. 13既然只跟人数有关,干脆把成绩全扔掉。这排格子代表候选组数 k,从 1 开始逐个试:分 k 组至少要 1+2+...+k 个人,记成 T(k)。只要 T(k) 不超过总人数 6,这个 k 就可行。
12. 14试 k = 1:至少要 1 = 1 个人。不超过 6,可行,标绿。继续看更大的 k。
13. 15试 k = 2:至少要 1+2 = 3 个人。不超过 6,可行,标绿。继续看更大的 k。
14. 16试 k = 3:至少要 1+2+3 = 6 个人。正好等于 6,人刚好用完,仍然可行,标绿。继续看更大的 k。
15. 17试 k = 4:至少要 1+2+3+4 = 10 个人,已经超过 6 了,凑不出来,标红。既然 T(k) 只增不减,再大的 k 更不可能,到此为止。最后一个绿色的 k = 3 就是答案。
16. 18逐个试当然行,但 n 能到十万,得用二分。把条件 k(k+1)/2 ≤ n 两边乘 2,写成 k²+k ≤ 2n,这里 2n = 12。在 0 到 6 之间二分,找最大的满足它的 k。
17. 19区间 [0, 6],中点向上取整 mid = 3。算 3²+3 = 12,和 12 比:不超过,说明分 3 组可行,这个 mid 本身可以成为答案。
18. 20因为可行,把下界 l 拉到 3,绿色候选也跟着到 3。答案至少 3,还想更大,所以去 mid 右边接着找。
19. 21区间 [3, 6],中点向上取整 mid = 5。算 5²+5 = 30,和 12 比:超过了,分 5 组人不够,mid 及它右边都不行。
20. 22因为不可行,把上界 r 压到 mid - 1 = 4,mid 和它右边整段排除。区间越缩越小。
21. 23区间 [3, 4],中点向上取整 mid = 4。算 4²+4 = 20,和 12 比:超过了,分 4 组人不够,mid 及它右边都不行。
22. 24因为不可行,把上界 r 压到 mid - 1 = 3,mid 和它右边整段排除。区间越缩越小。
23. 25l 和 r 碰头都停在 3,二分结束。绿色格 3 就是最大能分的组数,答案 = 3,和前面一块一块切出来的 3 组完全对上。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

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

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

复杂度

面试官可能追问