第 125 场 LeetCode 双周赛题解

A 超过阈值的最少操作数 I

排序然后查找第一个大于等于 k 的元素所在的位置

class Solution {
public:
    int minOperations(vector<int> &nums, int k) {
        sort(nums.begin(), nums.end());
        return lower_bound(nums.begin(), nums.end(), k) - nums.begin();
    }
};
1
2
3
4
5
6
7

---

B 超过阈值的最少操作数 II

模拟：用最小堆维护数组中的最小元素

class Solution {
public:
    int minOperations(vector<int> &nums, int k) {
        priority_queue<long long, vector<long long>, greater<long long>> heap;
        for (auto x: nums)
            heap.push(x);
        int res = 0;
        while (heap.size() > 1 && heap.top() < k) {
            res++;
            int x = heap.top();
            heap.pop();
            int y = heap.top();
            heap.pop();
            heap.push(2LL * min(x, y) + max(x, y));
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

C 在带权树网络中统计可连接服务器对数目

dfs：枚举 $c$ ，以 $c$ 的各邻接点为源点进行 $dfs$ ，设各次 $dfs$ 过程中路径和可以被 $signalSpeed$ 整除的节点数目为 $a_1,\cdots ,a_k$，则通过 $c$ 可连接的服务器对的数目为 ${\sum }_{1\le i<j\le k}{a}_i{a}_j$

class Solution {
public:
    vector<int> countPairsOfConnectableServers(vector<vector<int>> &edges, int signalSpeed) {
        int n = edges.size() + 1;
        vector<pair<int, int>> e[n];
        for (auto &ei: edges) {
            e[ei[0]].emplace_back(ei[1], ei[2]);
            e[ei[1]].emplace_back(ei[0], ei[2]);
        }
        int cnt;
        function<void(int, int, int)> dfs = [&](int cur, int pre, int ps) {//当前路径和为ps
            if (ps % signalSpeed == 0)
                cnt++;
            for (auto &[j, w]: e[cur])
                if (j != pre)
                    dfs(j, cur, ps + w);
        };
        vector<int> res(n);
        for (int r = 0; r < n; r++) {
            int s = 0;//a_1+...+a_(j-1)
            for (auto &[j, w]: e[r]) {
                cnt = 0;//a_j
                dfs(j, r, w);
                res[r] += s * cnt;
                s += cnt;
            }
        }
        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
26
27
28
29
30

---

D 最大节点价值之和

思维 + 贪心：考虑对树上的一条路径的各边进行操作时，相当于只对路径的两段点进行了异或操作，所以等价于每次操作可以对任意两点进行。将 $nums[i]\wedge k-nums[i]$ 按降序排序，然后两两一组进行操作，直到只剩一个元素或两个一组之和小于等于 $0$

class Solution {
public:
    long long maximumValueSum(vector<int> &nums, int k, vector<vector<int>> &edges) {
        vector<int> li;
        for (auto x: nums)
            li.push_back((x ^ k) - x);
        sort(li.begin(), li.end(), greater<int>());//降序排序
        long long res = accumulate(nums.begin(), nums.end(), 0LL);//原数组元素和
        long long d = 0;
        for (int i = 0; i + 1 < li.size(); i += 2)
            if (li[i] + li[i + 1] > 0) {//两两一组地进行操作
                d += li[i] + li[i + 1];
            } else
                break;
        return res + d;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17