力扣第 100 场双周赛

比赛时间 2023-03-18。本场周赛国服共 887 人 AK。

T1. 将钱分给最多的儿童（3 分）

解题思路

贪心 + 分类讨论。

由于数据范围比较小，我们可以直接由大到小枚举恰好 8 美元的儿童人数，第一个满足条件的即为答案。

设有 x 个儿童获得恰好 8 美元，则有 y 个（其中 y = children - x）儿童至少获得 1 美元且没有人获得 4 美元。有 8x + y <= money；

注意两个例外情况：

• 当 y = 0 时，但 8x < money 时，"所有的钱都必须被分配" 不成立；
• 当 y = 1 时，但 8x + 4 = money 时，"没有人获得 4 美元" 不成立；

时间复杂度：O(children)。

参考代码

class Solution {
    public int distMoney(int money, int children) {
        for (int x = children; x >= 0; x--) {
            int y = children - x;
            if (x * 8 + y > money) continue;
            int sumy = money - x * 8;
            if (y == 0 && sumy > 0) continue;
            if (y == 1 && sumy == 4) continue;
            return x;
        }
        return -1;
    }
}

T2. 最大化数组的伟大值（4 分）

解题思路

"田忌赛马" 经典问题。

相似题目: 870. 优势洗牌 https://leetcode.cn/problems/advantage-shuffle/

时间复杂度：O(nlogn)。

参考代码

class Solution {
    public int maximizeGreatness(int[] nums) {
        int n = nums.length;
        int[] nums2 = nums.clone();
        int[] perm = advantageCount(nums, nums2);

        int res = 0;
        for (int i = 0; i < n; i++) {
            if (perm[i] > nums2[i]) {
                res++;
            }
        }
        return res;
    }

    private int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;
        Arrays.sort(nums1);
        Integer[] id2 = IntStream.range(0, n).boxed().toArray(Integer[]::new);
        Arrays.sort(id2, Comparator.comparingInt(o -> nums2[o]));

        int[] res = new int[n];
        int l = 0, r = n - 1;
        for (int n1 : nums1) {
            if (n1 > nums2[id2[l]]) {
                res[id2[l]] = n1;
                l++;
            } else {
                res[id2[r]] = n1;
                r--;
            }
        }
        return res;
    }
}

T3. 标记所有元素后数组的分数（4 分）

解题思路

模拟。

排序后模拟（先按元素的大小升序排序，相同大小的元素按下标的大小升序排序）。

时间复杂度：O(nlogn)。

参考代码

class Solution {
    public long findScore(int[] nums) {
        int n = nums.length;

        // [i, val]
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(new int[]{i, nums[i]});
        }
        // Java 关于对象的排序是稳定排序
        list.sort(Comparator.comparingInt(o -> o[1]));

        long res = 0L;
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            int[] p = list.get(i);
            if (!visited[p[0]]) {
                res += p[1];
                if (p[0] - 1 >= 0) {
                    visited[p[0] - 1] = true;
                }
                if (p[0] + 1 < n) {
                    visited[p[0] + 1] = true;
                }
            }
        }
        return res;
    }
}

T4. 修车的最少时间（5 分）

解题思路

二分查找。

答案有单调性，可以二分答案。

时间复杂度：O(nlogU)。这里为了方便，U 直接取到了 2^63-1。

参考代码

class Solution {
    public long repairCars(int[] ranks, int cars) {
        long left = 0L;
        long right = Long.MAX_VALUE;
        while (left < right) {
            long mid = left + (right - left) / 2;
            // 边界二分 F, F,..., F, [T, T,..., T]
            // ----------------------^
            if (checkMid(ranks, cars, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    // 时间为 mid，能否完成修理
    private boolean checkMid(int[] ranks, int cars, long mid) {
        long k = 0;
        for (int r : ranks) {
            long n2 = mid / r;
            long n = (long) Math.sqrt(n2);
            k += n;
        }
        return k >= cars;
    }
}

（全文完）