leetcode-6133: maximum number of groupings

题目

题目连接

给你一个正整数数组 grades ,Represents the grades of some students in the university.你打算将 所有 Students are divided into groups 有序 non-empty grouping of,The order among the groups satisfies all of the following conditions：

第 i The total score of students in each group 小于 第 (i + 1) The total score of students in each group,true for all groups（Except for the last group）.
第 i The total number of students in a group 小于 第 (i + 1) The total number of students in a group,true for all groups（Except for the last group）.
Returns formable 最大 组数.

示例 1：

输入：grades = [10,6,12,7,3,5]
输出：3
解释：Below is the formation 3 A possible way of grouping：
- 第 1 The grades of students in each group are  grades = [12] ,总成绩：12 ,学生数：1
- 第 2 The grades of students in each group are  grades = [6,7] ,总成绩：6 + 7 = 13 ,学生数：2
- 第 3 The grades of students in each group are  grades = [10,3,5] ,总成绩：10 + 3 + 5 = 18 ,学生数：3 
It can be shown that it cannot be formed over 3 个分组.

示例 2：

输入：grades = [8,8]
输出：1
解释：只能形成 1 个分组,Because if to form 2 a group,would result in an equal number of students in each group.

解题

方法一：脑筋急转弯

如果从小到大排序
那么每次取 1个、2个、3个… Get the maximum amount you can get
而根grades具体是什么值,没有任何关系.
因此假设grades的值,是1、2、3、4、5、6、7…
第二次取2个元素,The resulting grouping sum must be greater than the first one taken1个元素

nis the number of all elements
Calculate with arithmetic progression (首项+末项)*项数/2<=n
Calculate the maximum number of groupsx即可

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

方法二：排序+贪心

从小到大排序
取1个、2个、3个…以此类推
Calculate the maximum number of groups that can be obtained

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