6323. Distribute Money to Maximum Children
给你一个整数 money ，表示你总共有的钱数（单位为美元）和另一个整数 children ，表示你要将钱分配给多少个儿童。
你需要按照如下规则分配：
- 所有的钱都必须被分配。
- 每个儿童至少获得 1 美元。
- 没有人获得 4 美元。
请你按照上述规则分配金钱，并返回 最多 有多少个儿童获得 恰好 8 美元。如果没有任何分配方案，返回 -1 。
测试样例
输入：money = 20, children = 3
输出：1
解释：
最多获得 8 美元的儿童数为 1 。一种分配方案为：
- 给第一个儿童分配 8 美元。
- 给第二个儿童分配 9 美元。
- 给第三个儿童分配 3 美元。
没有分配方案能让获得 8 美元的儿童数超过 1 。
解答：可以说这道题目是这周的关键了。没有wrong anser，排名基本不会难看。
- money == 8 * children 毫无问题，所有儿童8个硬币
- money > 8 * children 那么最后一个儿童拿所有多余硬币
- money < childen 那么无法满足题目要求
- 其他情况，由于题目范围很小直接暴力枚举。
class Solution {
public int distMoney(int money, int children) {
if (money == 8 * children) {
return children;
} else if (money > 8 * children) {
return children - 1;
} else if (money < children) {
return -1;
} else {
int res = 0;
for (int i = 0; i < children; ++i) {
int r = children - i, m = money - i * 8;
if (m < r) break;
else if (r == 1 && m == 4) {
continue;
} else {
res = i;
}
}
return res;
}
}
}6324. Maximize Greatness of an Array
给你一个下标从 0 开始的整数数组 nums 。你需要将 nums 重新排列成一个新的数组 perm 。
定义 nums 的 伟大值 为满足 0 <= i < nums.length 且 perm[i] > nums[i] 的下标数目。
请你返回重新排列 nums 后的 最大 伟大值。
测试样例：
输入：nums = [1,3,5,2,1,3,1]
输出：4
解释：
一个最优安排方案为 perm = [2,5,1,3,3,1,1] 。在下标为 0, 1, 3 和 4 处，都有 perm[i] > nums[i] 。因此我们返回 4 。
解答: 排序之后贪婪，最大的数覆盖次大的数
class Solution {
public int maximizeGreatness(int[] nums) {
Arrays.sort(nums);
int left = nums.length - 1, right = nums.length - 1;
int res = 0;
while (left >= 0) {
int cur = nums[right];
while (left >= 0 && nums[left] >= nums[right]) {
--left;
}
if (left >= 0) {
++res;
} else {
break;
}
--left;
--right;
}
return res;
}
}6351. Find Score of an Array After Marking All Elements
给你一个数组 nums ，它包含若干正整数。
一开始分数 score = 0 ，请你按照下面算法求出最后分数：
- 从数组中选择最小且没有被标记的整数。如果有相等元素，选择下标最小的一个。
- 将选中的整数加到 score 中。
- 标记 被选中元素，如果有相邻元素，则同时标记 与它相邻的两个元素 。
- 重复此过程直到数组中所有元素都被标记。
请你返回执行上述算法后最后的分数。
测试样例：
输入：nums = [2,1,3,4,5,2]
输出：7
解释：
我们按照如下步骤标记元素：
- 1 是最小未标记元素，所以标记它和相邻两个元素：[2,1,3,4,5,2] 。
- 2 是最小未标记元素，所以标记它和左边相邻元素：[2,1,3,4,5,2] 。
- 4 是仅剩唯一未标记的元素，所以我们标记它：[2,1,3,4,5,2] 。
总得分为 1 + 2 + 4 = 7 。
解答: 按照题意使用优先队列或者TreeSet，迭代直到没有剩余元素
class Solution {
public long findScore(int[] nums) {
TreeSet<Integer> set = new TreeSet<>((a, b) -> (nums[a] == nums[b] ? a.compareTo(b) : (nums[a] - nums[b])));
for (int i = 0; i < nums.length; ++i) {
set.add(i);
}
long res = 0;
while (!set.isEmpty()) {
int tmp = set.first();
res += nums[tmp];
set.remove(tmp);
if (tmp + 1 < nums.length) set.remove(tmp + 1);
if (tmp - 1 >= 0) set.remove(tmp - 1);
}
return res;
}
}6325. Minimum Time to Repair Cars
给你一个整数数组 ranks ，表示一些机械工的 能力值 。ranksi 是第 i 位机械工的能力值。能力值为 r 的机械工可以在 r * n2 分钟内修好 n 辆车。
同时给你一个整数 cars ，表示总共需要修理的汽车数目。
请你返回修理所有汽车 最少 需要多少时间。
注意：所有机械工可以同时修理汽车。
测试样例：
输入：ranks = [4,2,3,1], cars = 10
输出：16
解释：
- 第一位机械工修 2 辆车，需要 4 2 2 = 16 分钟。
- 第二位机械工修 2 辆车，需要 2 2 2 = 8 分钟。
- 第三位机械工修 2 辆车，需要 3 2 2 = 12 分钟。
- 第四位机械工修 4 辆车，需要 1 4 4 = 16 分钟。
16 分钟是修理完所有车需要的最少时间。
解答：由于工程师是并发工作，那么给的时间越多，能修理的车就越多。折半搜索关键点
class Solution {
public long repairCars(int[] ranks, int cars) {
long min = 0, max = 100L * cars * cars;
while (min < max) {
long mid = (min + max) / 2;
long couldRepair = 0;
for (int i = 0; i < ranks.length; ++i) {
couldRepair += (int) Math.sqrt(mid / ranks[i]);
}
if (couldRepair >= cars) {
max = mid;
} else {
min = mid + 1;
}
}
return min;
}
}