Skip to content

第 318 场周赛

比赛链接

Date: 2022-11-06

A 对数组执行操作

遍历即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> applyOperations(vector<int>& nums) {
        int n = nums.size();
        vector<int> ret;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                nums[i] *= 2;
                nums[i + 1] = 0;
            }
        }
        for (auto x : nums) if (x != 0) ret.push_back(x);
        ret.resize(n, 0);
        return ret;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def applyOperations(self, nums: List[int]) -> List[int]:
        ret = []
        for i in range(len(nums) - 1):
            if nums[i] == nums[i + 1]:
                nums[i] += nums[i]
                nums[i + 1] = 0
        for x in nums:
            if x != 0:
                ret.append(x)
        while len(ret) < len(nums):
            ret.append(0)
        return ret

复杂度分析

  • 时间复杂度：\(O(n)\)
  • 空间复杂度：\(O(n)\)

B 长度为 K 子数组中的最大和

滑动窗口维护程度为 \(k\) 的和，然后用哈希表记录其中每个数字出现的次数，\(cnt\) 记录出现的种类数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    using ll = long long;
    long long maximumSubarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        int cnt = 0;
        ll sum = 0, res = 0;
        for (int i = 0; i < nums.size(); i++) {
            int x = nums[i];
            mp[x]++;
            if (mp[x] == 1) cnt ++;
            sum += x;

            if (i - k >= 0) {
                mp[nums[i - k]]--;
                sum -= nums[i - k];
                if (mp[nums[i - k]] == 0) {
                    cnt--;
                }
            }
            if (cnt == k) {
                res = max(res, sum);
            }
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        mp = defaultdict(int)
        cnt, s, res = 0, 0, 0
        for i, x in enumerate(nums):
            mp[x] += 1
            if mp[x] == 1:
                cnt += 1
            s += x

            if i - k >= 0:
                mp[nums[i - k]] -= 1
                if mp[nums[i - k]] == 0:
                    cnt -= 1
                s -= nums[i - k]
            if cnt == k:
                res = max(res, s)
        return res

复杂度分析

  • 时间复杂度：\(O(n)\)
  • 空间复杂度：\(O(n)\)

C 雇佣 K 位工人的总代价

设置两个指针 \(l\) 和 \(r\)，分别指向左右两边的边界，然后用一个优先队列来维护候选集即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    long long totalCost(vector<int>& costs, int k, int candidates) {
        using ll = long long;
        using PLI = pair<ll, int>;
        priority_queue<PLI, vector<PLI>, greater<PLI>> q;
        ll res = 0;

        int n = costs.size();
        int l = 0, r = n - 1;
        while (l < candidates) {
            q.push({costs[l], l});
            l++;
        }
        while (r >= n - candidates && r >= l) {
            q.push({costs[r], r});
            r--;
        }
        for (int i = 0; i < k; i++) {
            res += q.top().first;
            int pos = q.top().second;
            q.pop();
            if (pos < l && l <= r) {
                q.push({costs[l], l});
                l++;
            }
            if (pos > r && l <= r) {
                q.push({costs[r], r});
                r--;
            }
        }
        return res;
    }
};

复杂度分析

  • 时间复杂度：\(O(n\log n)\)
  • 空间复杂度：\(O(n)\)

D 最小移动总距离

设 \(d[i][j]\) 表示前 \(i\) 个工厂修了 \(m\) 个机器人的代价。转移时：

\[d[i][j] = min_{k=0}^n (d[i - 1][k] + cost_{p=k+1}^j dist(p,i))\]
class Solution {
public:
    long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
        sort(robot.begin(), robot.end());
        sort(factory.begin(), factory.end());
        using ll = long long;
        int n = robot.size(), m = factory.size();
        vector<vector<ll>> d(m + 1, vector<ll>(n + 1, 1E15));
        d[0][0] = 0;
        ll res = 1E15;
        for (int i = 1; i <= m; i++) {
            int fac_pos = factory[i - 1][0], cnt = factory[i - 1][1];
            for (int j = 0; j <= n; j++) {
                d[i][j] = min(d[i][j], d[i - 1][j]);
            }
            for (int j = 0; j < n; j++) {
                ll sum = 0;
                for (int k = j; k < n; k++) {
                    if (k - j + 1 > cnt) break;
                    sum += abs(robot[k] - fac_pos);
                    d[i][k + 1] = min(d[i][k + 1], d[i - 1][j] + sum);
                }
            }
            res = min(res, d[i][n]);
        }
        return res;
    }
};

复杂度分析

  • 时间复杂度：\(O(n^2m)\)
  • 空间复杂度：\(O(nm)\)

另外这个题也可以用费用流来求解，把它视作一个带权二分图匹配问题。

当然，还有更巧妙地做法，是通过把工厂平铺成容量为 1 的工厂，这样 DP 会更好写。

本文访问 次