题目
给你一个正整数数组 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 个分组。
示例 2：
输入：grades = [8,8] 输出：1 解释：只能形成 1 个分组，因为如果要形成 2 个分组的话，会导致每个分组中的学生数目相等。
解题
方法一：脑筋急转弯
如果从小到大排序
那么每次取 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个…以此类推
计算能取得最大组数
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; } };
