第 87 场双周赛

比赛链接

A 统计共同度过的日子数

计算每个日期是一年中的第几天，然后将问题转换为两区间求交集即可。Python 可以直接调库。

C++Python

class Solution {
public:
    int countDaysTogether(string arriveAlice, string leaveAlice, string arriveBob, string leaveBob) {
        const int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        auto get = [&](string &s) {
            int month = stoi(s.substr(0, 2));
            int day = stoi(s.substr(3));
            int cnt = 0;
            for (int i = 0; i < month - 1; i++) {
                cnt += days[i];
            }
            return cnt + day;
        };
        int l1 = get(arriveAlice), r1 = get(leaveAlice);
        int l2 = get(arriveBob), r2 = get(leaveBob);
        return max(0, min(r1, r2) - max(l1, l2) + 1);
    }
};

class Solution:
def countDaysTogether(self, arriveAlice: str, leaveAlice: str, arriveBob: str, leaveBob: str) -> int:
    def calc_dt(date: str) -> datetime.datetime:
        return datetime.datetime.strptime(date, '%m-%d')  # 默认是 1900 年（平年）
    return max((calc_dt(min(leaveAlice, leaveBob)) - calc_dt(max(arriveAlice, arriveBob))).days + 1, 0)

B 运动员和训练师的最大匹配数

运动员从小到大依次考虑，如果一个小的运动员都找不到训练师，那么大的运动会更不会找到。所以只需要考虑给当前这个运动员找一个能力值最小且可以满足要求的训练师匹配即可。

时间复杂度 \(O(n\log n+ m\log m)\)

C++Python

class Solution {
public:
    int matchPlayersAndTrainers(vector<int>& players, vector<int>& trainers) {
        sort(players.begin(), players.end());
        sort(trainers.begin(), trainers.end());
        int res = 0;
        for (int i = 0, j = 0; i < players.size(); i++) {
            while (j < trainers.size() && trainers[j] < players[i]) {
                j++;
            }
            if (j < trainers.size() && trainers[j] >= players[i]) {
                res++;
                j++;
                continue;
            } else {
                break;
            }
        }
        return res;
    }
};

class Solution:
    def matchPlayersAndTrainers(self, players: List[int], trainers: List[int]) -> int:
        players.sort()
        trainers.sort()
        n, m = len(players), len(trainers)
        j = 0
        res = 0
        for i in range(n):
            while j < m and trainers[j] < players[i]:
                j += 1
            if j < m and trainers[j] >= players[i]:
                res += 1
                j += 1
            else:
                break
        return res

C 按位或最大的最小子数组长度

容易想到随着 \(i\) 减少，\(i + answer[i] - 1\) 也就是右边界是非递增的。所以，我们从大到小遍历 \(i\)，全程维护一个数组 \(cnt\)，\(cnt[k]\) 表示 \([i,j]\) 中每个数字二进制表示中第 \(k\) 位为 1 的数字个数。

每次 \(i\) 递减变化时，我们尝试缩减 \(j\)，从 \(cnt\) 中减去 \(nums[j]\) 的贡献，如果使得 \(cnt\) 中非 0 个数减少，那么 \(nums[j]\) 不应当被移除，否则我们移除 \(nums[j]\)

复杂度 \(O(n\log n)\)

C++Python

class Solution {
public:
    vector<int> smallestSubarrays(vector<int>& nums) {
        const int N = 31;
        int n = nums.size();
        vector<int> cnt(N), res(n);
        auto check = [&](int x) {
            for (int i = 0; i < N; i++) {
                if ((x >> i & 1) && cnt[i] == 1) {
                    return false;
                }
            }
            return true;
        };
        for (int i = n - 1, j = n - 1; i >= 0; i--) {
            for (int k = 0; k < N; k++) {
                if (nums[i] >> k & 1) {
                    cnt[k]++;
                }
            }
            while (j > i && check(nums[j])) {
                for (int k = 0; k < N; k++) {
                    if (nums[j] >> k & 1) {
                        cnt[k]--;
                    }
                }
                j--;
            }
            res[i] = j - i + 1;
        }
        return res;
    }
};

class Solution:
    def smallestSubarrays(self, nums: List[int]) -> List[int]:
        N = 31
        n = len(nums)
        cnt = [0] * N 
        res = [0] * n

        def check(x):
            for i in range(N):
                if x >> i & 1 and cnt[i] == 1:
                    return False
            return True

        j = n - 1
        for i in range(n - 1, -1, -1):
            for k in range(N):
                if nums[i] >> k & 1:
                    cnt[k] += 1
            while j > i and check(nums[j]):
                for k in range(N):
                    if nums[j] >> k & 1:
                        cnt[k] -= 1
                j -= 1
            res[i] = j - i + 1
        return res

D 完成所有交易的初始最少钱数

对于所有 \(cost > cashback\) 的交易，都会造成亏损，很显然它们应该优先去交易，才会使得初始 \(money\) 最大。设 \(totLoss = \sum max(cost - cashback, 0)\)

然后，最关键的交易可能发生在两个时刻：

1. 所有 \(cost > cashback\) 的交易中的最后一个
2. 所有 \(cost < cashback\) 的交易中的第一个

对于第一种类型，所需要满足的初始 \(money = totLoss + cashback\)

而对于第二种类型，所需要满足的初始 \(money = totLoss + cost\)

因此，为了使得 \(money\) 最小，并且可以满足所有交易顺序，那么应该去寻找 \(totLoss + \max_{i=0}^{n-1} min(cost_i, cashback_i)\)

时间复杂度为 \(O(n)\)

C++Python

class Solution {
public:
    using ll = long long;
    long long minimumMoney(vector<vector<int>>& transactions) {
        ll totLoss = 0;
        int buff = 0;
        for (auto &v : transactions) {
            totLoss += max(v[0] - v[1], 0);
            buff = max(buff, min(v[0], v[1]));
        }   
        return totLoss + buff;
    }
};

class Solution:
    def minimumMoney(self, transactions: List[List[int]]) -> int:
        totLoss = 0
        buff = 0
        for cost, cashback in transactions:
            totLoss += max(cost - cashback, 0)
            buff = max(buff, min(cost, cashback))
        return totLoss + buff

本文访问 次