题目

题目连接

给你一个正整数数组 grades ，表示大学中一些学生的成绩。你打算将 所有 学生分为一些 有序 的非空分组，其中分组间的顺序满足以下全部条件：

第 i 个分组中的学生总成绩 小于 第 (i + 1) 个分组中的学生总成绩，对所有组均成立（除了最后一组）。
第 i 个分组中的学生总数 小于 第 (i + 1) 个分组中的学生总数，对所有组均成立（除了最后一组）。
返回可以形成的 最大 组数。

示例 1：

输入：grades = [10,6,12,7,3,5]
输出：3
解释：下面是形成 3 个分组的一种可行方法：
- 第 1 个分组的学生成绩为 grades = [12] ，总成绩：12 ，学生数：1
- 第 2 个分组的学生成绩为 grades = [6,7] ，总成绩：6 + 7 = 13 ，学生数：2
- 第 3 个分组的学生成绩为 grades = [10,3,5] ，总成绩：10 + 3 + 5 = 18 ，学生数：3 
可以证明无法形成超过 3 个分组。
1
2
3
4
5
6
7

示例 2：

输入：grades = [8,8]
输出：1
解释：只能形成 1 个分组，因为如果要形成 2 个分组的话，会导致每个分组中的学生数目相等。
1
2
3

解题

方法一：脑筋急转弯

如果从小到大排序
那么每次取 1个、2个、3个… 就能得到最大的能取得的数量
而根grades具体是什么值，没有任何关系。
因此假设grades的值，是1、2、3、4、5、6、7…
第二次取2个元素，得到的分组和一定是大于第一次取的1个元素

n为所有元素个数
用等差数列计算 (首项+末项)*项数/2<=n
计算得到最大组数x即可

class Solution {
public:
    int maximumGroups(vector<int>& grades) {
        int len=grades.size();
        return sqrt(2*len+0.25)-0.5;
    }
};
1
2
3
4
5
6
7

方法二：排序+贪心

从小到大排序
取1个、2个、3个…以此类推
计算能取得最大组数

class Solution {
public:
    int maximumGroups(vector<int>& grades) {
        sort(grades.begin(),grades.end());
        int res=1,n=grades.size();
        
        int preVal=grades[0];
        int preCount=1;
        
        int curVal=0;
        int curCount=0;

        int i=1;
        while(i<n){
            while(true){
                if(curCount>preCount&&curVal>preVal) break;
                if(i==n) return res;
                curVal+=grades[i];
                curCount++;
                i++;
            }
            
            res++;
            preVal=curVal;
            preCount=curCount;
            
            curVal=0;
            curCount=0;
            
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33