二分法中等 LeetCode6133. 分组的最大数量

6133. 分组的最大数量

描述

给你一个正整数数组 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 <= grades.length <= 105
1 <= grades[i] <= 105

分析

数组元素的大小不重要，只要判断数组长度能够凑出多少个分组。
二分法计算

class Solution {
    
    public int maximumGroups(int[] grades) {
    
        int n = grades.length;
        int left = 1, right = n;
        while (left < right) {
    
            int mid = (right - left + 1) / 2 + left;
            if ((1+mid) > 2 * n / mid) {
    
                right = mid - 1;
            } else if ((1+mid) < 2 * n / mid){
    
                left = mid;
            } else {
    
                return mid;
            }
        }
        return left;
    }
}