Skip to content

第 316 场周赛

比赛链接

Date: 2022-10-23

A 判断两个事件是否存在冲突

将时间转换为数字（距离 00:00 所经过的分钟数），然后判断区间是否相交即可。

判断两区间 [l1, r1], [l2, r2] 是否相交的充要条件：max(l1, l2) <= min(r1, r2)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int get(string t) {
        int h = stoi(t.substr(0, 2));
        int m = stoi(t.substr(3));
        return h * 60 + m;
    }
    bool haveConflict(vector<string>& event1, vector<string>& event2) {
        int l1 = get(event1[0]), r1 = get(event1[1]);
        int l2 = get(event2[0]), r2 = get(event2[1]);
        return max(l1, l2) <= min(r1, r2);
        if (l1 > l2) swap(l1, l2), swap(r1, r2);
    }
};

1
2
3
4
5
6
7
class Solution:
    def haveConflict(self, a: List[str], b: List[str]) -> bool:
        def get(s):
            h = int(s[0:2])
            m = int(s[3:])
            return h * 60 + m
        return max(get(a[0]), get(b[0])) <= min(get(a[1]), get(b[1]))

还有一种简单的办法是，直接使用字符串来比大小。

1
2
3
class Solution:
    def haveConflict(self, event1: List[str], event2: List[str]) -> bool:
        return not (event1[0] > event2[1] or event2[0] > event1[1])

B 最大公因数等于 K 的子数组数目

区间长度只有 1000，所以直接 \(n^2\) 枚举即可。注意过程中可以当 \(g < k\) 或者 \(g \% k \neq 0\) 时直接 break。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int subarrayGCD(vector<int>& nums, int k) {
        int res = 0;
        for (int i = 0; i < nums.size(); i++) {
            int g = nums[i];
            for (int j = i; j < nums.size(); j++) {
                g = gcd(g, nums[j]);
                if (g == k) {
                    res++;
                }
                if (g < k || g % k != 0) break; 
            }
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def subarrayGCD(self, nums: List[int], k: int) -> int:
        res = 0
        for i in range(len(nums)):
            g = nums[i]
            for j in range(i, len(nums)):
                g = gcd(g, nums[j])
                if g == k:
                    res += 1
                elif g < k or g % k != 0:
                    break
        return res

C 使数组相等的最小开销

枚举每个 \(x\)，求出所有数字变为 \(x\) 的代价总和。我们不能直接暴力去求。

容易想到，我们只需要枚举 \(nums\) 中的每个数字作为 \(x\) 即可。因此，从小到大枚举 \(nums\) 中的每个数字 \(x\)，我们现在只求所有小于 \(x\) 的数字变为 \(x\) 的代价总和，剩余大于 \(x\) 的代价总和之后倒序来算。

设小于 \(x\) 的最大数字是 \(last\)，\(cur\) 是小于 \(last\) 的数字变为 \(last\) 所需的代价总和，\(sum\) 是所有小于等于 \(last\) 的数字变化一次所需的代价总和。那么，所有小于 \(x\) 的数字变为 \(x\) 的代价总和就是：

\[cur + sum * (x - last)\]

同理，我们可以求出所有大于 \(x\) 的数字变为 \(x\) 所需的代价总和。

总体复杂度 \(O(n\log n)\)。

 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:
    using ll = long long;
    long long minCost(vector<int>& nums, vector<int>& cost) {
        map<int, ll> costs, ret;
        for (int i = 0; i < nums.size(); i++) {
            costs[nums[i]] += cost[i];
        }
        ll cur = 0, sum = 0, last = -1;
        for (auto [k, v] : costs) {
            if (last != -1) {
                cur = cur + sum * (k - last);
            }
            sum += v;
            ret[k] = cur;
            last = k;
        }
        auto it = costs.rbegin();
        cur = sum = 0; last = -1;
        ll res = LLONG_MAX;
        while (it != costs.rend()) {
            ll k = it->first, v = it->second;
            if (last != -1) {
                cur = cur + sum * (last - k);
            }
            sum += v;
            ret[k] += cur;
            last = k;
            res = min(res, ret[k]);
            it++;
        }
        return res;
    }
};

另外，这个题也可以直接用中位数去计算，本质上和这个题一样的：货仓选址

我们可以看做是，每个数字都有 \(cost\) 个，移动其中的一个会消耗 1 的能量。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def minCost(self, nums: List[int], cost: List[int]) -> int:
        a = list(zip(nums, cost))
        a.sort()
        tot = sum(cost)
        pos, psum = 0, 0
        for k, v in a:
            psum += v
            if psum >= tot // 2:
                pos = k
                break
        res = 0
        for k, v in a:
            res += abs(k - pos) * v
        return res

D 使数组相似的最少操作次数

没个数字都是 +2、-2 的操作，因此所有数字的奇偶性不会改变。

设两个数组为 \(a\) 和 \(b\)，我们将他们分别拆为奇偶两个数组：\(ao\), \(ae\), \(bo\), \(be\)。其中 \(ao\) 表示 \(a_odd\),\(ae\) 表示 \(a_even\)。

然后，\(ao\) 中的数字最终应该要变为 \(bo\), \(ae\) 中的数字最终应该要变为 \(be\)，因为要尽量少的去操作，所以排序后数字应该是一一对应的。

这样，就可以很快的算出所需要的加减次数了。

时间复杂度 \(O(n\log n)\)。

class Solution {
public:
    using ll = long long;
    long long makeSimilar(vector<int>& a, vector<int>& b) {
        vector<int> ao, ae, bo, be;
        for (auto x : a) {
            if (x & 1) ao.push_back(x);
            else ae.push_back(x);
        }
        for (auto x : b) {
            if (x & 1) bo.push_back(x);
            else be.push_back(x);
        }
        sort(ao.begin(), ao.end());
        sort(ae.begin(), ae.end());
        sort(bo.begin(), bo.end());
        sort(be.begin(), be.end());
        ll res = 0;
        for (int i = 0; i < ao.size(); i++) {
            if (ao[i] >= bo[i]) res += (ao[i] - bo[i]) / 2;
        }
        for (int i = 0; i < ae.size(); i++) {
            if (ae[i] >= be[i]) res += (ae[i] - be[i]) / 2;
        } 
        return res;
    }
};

 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
class Solution:
    def makeSimilar(self, nums: List[int], target: List[int]) -> int:
        ao, ae, bo, be = [], [], [], []
        for x in nums:
            if x & 1:
                ao.append(x)
            else:
                ae.append(x)
        for x in target:
            if x & 1:
                bo.append(x)
            else:
                be.append(x)
        ao.sort()
        ae.sort()
        bo.sort()
        be.sort()
        res = 0
        for i in range(len(ao)):
            if ao[i] > bo[i]:
                res += (ao[i] - bo[i]) // 2
        for i in range(len(ae)):
            if ae[i] > be[i]:
                res += (ae[i] - be[i]) // 2
        return res

小结

这周两个 hard，还都是比较偏向于思维题。思路慢了很多，因为这几周没有每天坚持做题了。
本文访问 次