郑州网站建设招标,备案后修改网站名称,建设厅网站企业诚信分值,张家界市网站建设设计题目#xff1a;
给你一个下标从 0 开始、长度为 n 的数组 usageLimits 。
你的任务是使用从 0 到 n - 1 的数字创建若干组#xff0c;并确保每个数字 i 在 所有组 中使用的次数总共不超过 usageLimits[i] 次。此外#xff0c;还必须满足以下条件#xff1a;
每个组必须…题目
给你一个下标从 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 10^5 1 usageLimits[i] 10^9
java代码
class Solution {public int maxIncreasingGroups(ListInteger usageLimits) {int n usageLimits.size();Collections.sort(usageLimits);int[] nums new int[n];for (int i n - 1 ; i 0; i--) {nums[n - 1 - i] usageLimits.get(i);}int ret 1;int l 1;int r n;while (l r) {int m l (r - l) / 2 1;if (check(nums, m)) {l m;ret Math.max(m, ret);} else {r m - 1;}}return ret;}public boolean check(int[] nums, int k) {int n nums.length;int d 0;for (int i 0; i n; i) {if (Math.max(k - i, 0) nums[i]) {if (d 0) {d - nums[i] - Math.max(k - i, 0);}continue;} d k - i - nums[i];}return d 0;}
}
