leetcode biweekly contest 100

本场周赛题目质量太差，题目都太过于简单。

2591. 将钱分给最多的儿童

给你一个整数 money ，表示你总共有的钱数（单位为美元）和另一个整数 children ，表示你要将钱分配给多少个儿童。

你需要按照如下规则分配：

所有的钱都必须被分配。
每个儿童至少获得 1 美元。
没有人获得 4 美元。

请你按照上述规则分配金钱，并返回最多有多少个儿童获得恰好 8 美元。如果没有任何分配方案，返回 -1 。

示例 1：

输入：money = 20, children = 3
输出：1
解释：
最多获得 8 美元的儿童数为 1 。一种分配方案为：
- 给第一个儿童分配 8 美元。
- 给第二个儿童分配 9 美元。
- 给第三个儿童分配 3 美元。
没有分配方案能让获得 8 美元的儿童数超过 1 。

示例 2：

输入：money = 16, children = 2
输出：2
解释：每个儿童都可以获得 8 美元。

提示：

1 <= money <= 200
2 <= children <= 30

地址

https://leetcode.cn/contest/biweekly-contest-100/problems/distribute-money-to-maximum-children/

题意

直接遍历

思路

直接模拟即可，但是这个题目比较恶心的检测条件较多，假设最多有 $x$ 个人拿到 $8$ 元，则需要检测如下条件
- 剩下的人为 $n - x$，剩下的人最少每个人有 $1$ 元，则此时 $8x + n - x \le money$；
- 剩余 $x = n$，此时 $8x > money$ 时，最多只能有 $n - 1$ 个人拿到 $8$ 元；
- 当剩余 $1$ 个人时，此时剩余的钱为 $4$ 时也不能进行分配；
复杂度分析：

时间复杂度：$O(n)$。
空间复杂度：$O(1)$。

代码

class Solution {
public:
    int distMoney(int money, int children) {
        int x = money / 8;
        if (money < children) {
            return -1;
        }
        for (int i = children; i >= 1; i--) {
            int x = children - i;
            if (x == 0 && money - i * 8 > 0) {
                continue;
            }
            if (i * 8 > money || money - i * 8 < x) {
                continue;
            }
            if (x == 1 && money - i * 8 == 4) {
                continue;
            }
            return i;
        }
        return 0;
    }
};

2592. 最大化数组的伟大值

给你一个下标从 0 开始的整数数组 nums 。你需要将 nums 重新排列成一个新的数组 perm 。

定义 nums 的 伟大值 为满足 0 <= i < nums.length 且 perm[i] > nums[i] 的下标数目。

请你返回重新排列 nums 后的最大伟大值。

示例 1：

输入：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 。

示例 2：

输入：nums = [1,2,3,4]
输出：3
解释：最优排列为 [2,3,4,1] 。
在下标为 0, 1 和 2 处，都有 perm[i] > nums[i] 。因此我们返回 3 。

提示：

1 <= nums.length <= 105
0 <= nums[i] <= 109

地址

https://leetcode.cn/contest/biweekly-contest-100/problems/maximize-greatness-of-an-array/

题意

排序 + 贪心策略

思路

贪心即可，首先将数组按照从小到大进行排列，首先我们知道最小的 $nums[i]$ 应该与 $nums[i]$ 稍大的数进行配对，且优先从最小的开始配对，这样才能保证配对的数目最多，我们优先从最小的元素和次小的元素配对。
复杂度分析：

时间复杂度：$O(n \log n)$，其中 $n$ 为数组的长度，排序的时间复杂度为 $O(n \log n)$。
空间复杂度：$O(\log n)$，其中 $n$ 为为数组的长度。排序需要的空间为 $O(\log n)$。

代码

class Solution {
public:
    int maximizeGreatness(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        sort(nums.begin(), nums.end());
        for (int i = 0, j = 0; i < n; i++) {
            while (j < n && nums[i] == nums[j]) {
                j++;
            }
            if (j < n && nums[j] > nums[i]) {
                ans++;
                j++;
            } else {
                break;
            }
        }
        return ans;
    }
};

2593. 标记所有元素后数组的分数

显示英文描述

我的提交返回竞赛

通过的用户数1492
尝试过的用户数1871
用户总通过次数1566
用户总提交次数3303
题目难度****Medium

给你一个数组 nums ，它包含若干正整数。

一开始分数 score = 0 ，请你按照下面算法求出最后分数：

从数组中选择最小且没有被标记的整数。如果有相等元素，选择下标最小的一个。
将选中的整数加到 score 中。
标记 被选中元素，如果有相邻元素，则同时标记 与它相邻的两个元素 。
重复此过程直到数组中所有元素都被标记。

请你返回执行上述算法后最后的分数。

示例 1：

输入：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 。

示例 2：

输入：nums = [2,3,5,1,3,2]
输出：5
解释：我们按照如下步骤标记元素：
- 1 是最小未标记元素，所以标记它和相邻两个元素：[2,3,5,1,3,2] 。
- 2 是最小未标记元素，由于有两个 2 ，我们选择最左边的一个 2 ，也就是下标为 0 处的 2 ，以及它右边相邻的元素：[2,3,5,1,3,2] 。
- 2 是仅剩唯一未标记的元素，所以我们标记它：[2,3,5,1,3,2] 。
总得分为 1 + 2 + 2 = 5 。

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 106

地址

https://leetcode.cn/contest/biweekly-contest-100/problems/find-score-of-an-array-after-marking-all-elements/

题意

模拟+ 优先队列

思路

题目比较简单，直接按照题意要求，将所有的元素都压入到优先队列中，初始化时，所有元素都未被标记过，每次从队列中弹出最小的元素：
- 如果该元素未被标记过，并将其左右相邻的元素都进行标记。
- 如果该元素被标记过，则继续下一个弹出操作；
复杂度分析：

时间复杂度：$O(n \log n)$，其中 $n$ 为数组的长度。
空间复杂度：$O(n)$，其中 $n$ 为数组的长度。

代码

class Solution {
public:
    long long findScore(vector<int>& nums) {
        int n = nums.size();
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        vector<bool> visit(n, false);
        for (int i = 0; i < n; i++) {
            pq.emplace(nums[i], i);
        }
        long long ans = 0;
        while (!pq.empty()) {
            auto [val, idx] = pq.top();
            pq.pop();
            if (visit[idx]) {
                continue;
            } else {
                ans += val;
                visit[idx] = true;
                if (idx - 1 >= 0) {
                    visit[idx - 1] = true;
                }
                if (idx + 1 < n) {
                    visit[idx + 1] = true;
                }
            }
        }
        return ans;
    }
};

2594. 修车的最少时间

给你一个整数数组 ranks ，表示一些机械工的 能力值 。ranksi 是第 i 位机械工的能力值。能力值为 r 的机械工可以在 r * n2 分钟内修好 n 辆车。

同时给你一个整数 cars ，表示总共需要修理的汽车数目。

请你返回修理所有汽车最少需要多少时间。

注意：所有机械工可以同时修理汽车。

示例 1：

输入：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 分钟是修理完所有车需要的最少时间。

示例 2：

输入：ranks = [5,1,8], cars = 6
输出：16
解释：
- 第一位机械工修 1 辆车，需要 5 * 1 * 1 = 5 分钟。
- 第二位机械工修 4 辆车，需要 1 * 4 * 4 = 16 分钟。
- 第三位机械工修 1 辆车，需要 8 * 1 * 1 = 8 分钟。
16 分钟时修理完所有车需要的最少时间。

提示：

1 <= ranks.length <= 105
1 <= ranks[i] <= 100
1 <= cars <= 106

地址

https://leetcode.cn/contest/biweekly-contest-100/problems/minimum-time-to-repair-cars/

题意

二分查找

思路

想来想去确实没有特别好的办法，直接暴力二分查找。因为题目中的时间符合线性规则，大于某个时间点一定可以满足，小于某个时间点一定不满足，我们尝试时间 $t$ 下可以修理的最多的汽车数目是否大于 $cars$ 即可。
复杂度分析：

时间复杂度：$O(n \times \log U)$，其中$ n$ 表示数组的长度，$U$ 表示题目中时间的最大值。
空间复杂度：$O(1)$。

class Solution {
public:
    bool check(vector<int>& ranks, int cars, long long tot) {
        int n = ranks.size();
        long long x = 0;
        for (int i = 0; i < n; i++) {
            x += sqrt((double)tot / ranks[i]);
        }
        if (x >= cars) {
            return true;
        }
        return false;
    }
    
    long long repairCars(vector<int>& ranks, int cars) {
        sort(ranks.begin(), ranks.end());
        int n = ranks.size();
        long long L = 0;
        long long R = LONG_MAX;
        long long ans = 0;
        while (L <= R) {
            long long  mid = L + (R - L) / 2;
            if (check(ranks, cars, mid)) {
                R = mid - 1;
                ans = mid;
            } else {
                L = mid + 1;
            }
        }
        return ans;
    }
};

欢迎关注和打赏，感谢支持！

关注我的博客: http://whistle-wind.com/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 力扣周赛题解

← leetcode weekly contest 336 leetcode weekly contest 337 →

扫描二维码，分享此文章