class Solution {
public:
int maxIncreasingGroups(vector<int>& usageLimits) {
}
};
6955. 长度递增组的最大数目
给你一个下标从 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 <= 1051 <= usageLimits[i] <= 109原站题解
java 解法, 执行用时: 120 ms, 内存消耗: 53.8 MB, 提交时间: 2023-07-24 10:40:15
class Solution {
public int maxIncreasingGroups(List<Integer> usageLimits) {
Collections.sort(usageLimits);
long ans = 0, s = 0;
for ( int i:usageLimits ) {
s += (long)i;
if ( s >= (ans+2) * (ans+1) / 2 ) {
ans++;
}
}
return (int)ans;
}
}
python3 解法, 执行用时: 176 ms, 内存消耗: 31.3 MB, 提交时间: 2023-07-24 10:38:58
class Solution:
def maxIncreasingGroups(self, usageLimits: List[int]) -> int:
usageLimits.sort()
curr, ans = 0, 0
for n in usageLimits:
curr += n
if curr >= ans + 1:
ans += 1
curr -= ans
return ans
golang 解法, 执行用时: 152 ms, 内存消耗: 9.5 MB, 提交时间: 2023-07-24 10:37:22
func maxIncreasingGroups(usageLimits []int) int {
sort.Ints(usageLimits)
curr, ans := 0, 0
for _, n := range usageLimits {
curr += n
if curr>=ans+1 {
ans += 1
curr -= ans
}
}
return ans
}
python3 解法, 执行用时: 1624 ms, 内存消耗: 31.4 MB, 提交时间: 2023-07-24 10:36:57
# 排序 + 二分
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