2790-长度递增组的最大数目

给你一个下标从 0 开始、长度为 n 的数组 usageLimits 。

你的任务是使用从 0 到 n - 1 的数字创建若干组，并确保每个数字 i 在 所有组 中使用的次数总共不超过
usageLimits[i] 次。此外，还必须满足以下条件：

每个组必须由不同的数字组成，也就是说，单个组内不能存在重复的数字。
每个组（除了第一个）的长度必须 严格大于 前一个组。

在满足所有条件的情况下，以整数形式返回可以创建的最大组数。

示例 1：

**输入：** usageLimits = [1,2,5]
**输出：** 3
**解释：** 在这个示例中，我们可以使用 0 至多一次，使用 1 至多 2 次，使用 2 至多 5 次。
一种既能满足所有条件，又能创建最多组的方式是： 
组 1 包含数字 [2] 。
组 2 包含数字 [1,2] 。
组 3 包含数字 [0,1,2] 。 
可以证明能够创建的最大组数是 3 。 
所以，输出是 3 。

示例 2：

**输入：**usageLimits = [2,1,2]
**输出：** 2
**解释：** 在这个示例中，我们可以使用 0 至多 2 次，使用 1 至多 1 次，使用 2 至多 2 次。
一种既能满足所有条件，又能创建最多组的方式是： 
组 1 包含数字 [0] 。 
组 2 包含数字 [1,2] 。
可以证明能够创建的最大组数是 2 。 
所以，输出是 2 。

示例 3：

**输入：**usageLimits = [1,1]
**输出：** 1
**解释：** 在这个示例中，我们可以使用 0 和 1 至多 1 次。 
一种既能满足所有条件，又能创建最多组的方式是：
组 1 包含数字 [0] 。
可以证明能够创建的最大组数是 1 。 
所以，输出是 1 。

提示：

1 <= usageLimits.length <= 105
1 <= usageLimits[i] <= 109

对于一个给定的usageLimits，我们只在乎usageLimits中数字的大小，并不在乎它实际所对应的值是多少，假设我们要满足groups=3，则最小目标序列为[3,2,1]，满足要求的usageLimits可以为[4,5,6],[3,2,1,5]… 问题可以重新描述为，对于一个给定的usageLimits和groups，能否从usageLimits中找到对应的最小目标序列target，然后对groups进行二分即可。

以usageLimits=[2,2,2]，groups=3为例，groups=3所对应的最小目标序列target=[3,2,1]

usageLimits中的值可以和target中的值一一对应，两者之间的大小关系可分为以下两类：

usageLimits[i] >= groups[i]，则多余的部分可用于补充前方缺口如图一，不可用于后方因为后续所有的数据均包含当前数字，补充后方缺口必然造成重复，如图二。如果前方不存在缺口则应丢弃
usageLimits[i] < groups[i]，记录缺口大小，等待后方多余多余数据来填补缺口

这一行需要居中 2. 记缺口大小为gap，gap<=0,因为gap只能被后方的数据修补，而无法主动修补后方的缺口 gap=\left\{ \begin{aligned} &min(gap + usageLimits[i]-target[i], 0),&usageLimits[i] \geq target[i] \\ &gap + usageLimits[i]-target[i], &usageLimits[i] < target[i] \\ \end{aligned} \right.

如果usageLimits[i]长度大于target，多余部分所对应的target[i]视作0

[]class Solution:
    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:
        usageLimits.sort(reverse = True)

        def check(n : int) -> bool:
            gap = 0
            for x in usageLimits:
                gap = min(gap + x - n, 0)
                if n > 0:
                    n -= 1
            return gap >= 0
        
        lower, upper = 0, len(usageLimits)
        while lower < upper:
            mid = int((lower + upper + 1) / 2)
            lower, upper = (mid, upper) if check(mid) else (lower, mid - 1)
        
        return lower