鸭梨公共文档

主题

第 338 场周赛 ​

6354. K 件物品的最大和 ​

分类讨论，如果 numOnes、numZeros 分别为 aa、bb。如果 a+b⩾ka + b \geqslant k，那么答案就是 min⁡(a, k)\min(a,\, k)，否则需要减去 k−(a+b)k-(a+b)，也就是 a−(k−(a+b))=2a+b−ka-(k-(a+b)) = 2a+b-k。

cpp
class Solution {
public:
    int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
        return (numOnes + numZeros >= k) ? min(numOnes, k) : 2 * numOnes + numZeros - k;
    }
};

6355. 质数减法运算 ​

贪心，质数可以直接打表，每次尽可能减去一个较小的质数，如果不满足条件直接返回 false。

打表代码：

python
res = []
for i in range(2, 1000):
    flag = True
    for j in range(2, i):
        if i % j == 0:
            flag = False
            break
    if flag:
        res.append(i)
print(res)

下面是 C++ 代码：

cpp
int primes[] = {2,   3,   5,   7,   11,  13,  17,  19,  23,  29,  31,  37,  41,
                43,  47,  53,  59,  61,  67,  71,  73,  79,  83,  89,  97,  101,
                103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167,
                173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239,
                241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313,
                317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397,
                401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467,
                479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569,
                571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643,
                647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
                739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823,
                827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
                919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997};

class Solution {
public:
    bool primeSubOperation(vector<int>& nums) {
        int n = (int)nums.size();
        for (int i = n - 1; i > 0; --i) {
            // 如果 nums[i] > nums[i - 1]，就不需要操作
            if (nums[i] > nums[i - 1]) continue;
            int min_p = nums[i - 1] - nums[i];
            int max_p = nums[i - 1];
            bool flag = false;
            for (int j = 0; j < 168; ++j) {
                // 如果这个质数在 [min_p, max_p] 之间，那么就减去这个质数
                if (primes[j] > min_p && primes[j] < max_p) {
                    nums[i - 1] -= primes[j];
                    flag = true;
                    break;
                }
            }
            // 如果没有找到合适的质数，那么就返回 false
            if (!flag) return false;
        }
        return true;
    }
};

6357. 使数组元素全部相等的最少操作次数 ​

前缀和 + 二分，这题小心溢出，所以尽可能使用 long long。

cpp
#define ll long long

class Solution {
public:
    vector<ll> minOperations(vector<int>& nums, vector<int>& queries) {
        sort(nums.begin(), nums.end());
        ll n = (ll)nums.size();
        // 计算前缀和
        vector<ll> prefix(n + 1, 0);
        for (ll i = 1; i <= n; ++i) {
            prefix[i] = prefix[i - 1] + nums[i - 1];
        }
        vector<ll> res;
        for (auto beg = queries.cbegin(); beg != queries.cend(); ++beg) {
            ll q = *beg;
            ll l = 0, r = n - 1;
            while (l < r) {
                ll mid = (l + r) >> 1;
                if (nums[mid] < q)
                    l = mid + 1;
                else
                    r = mid;
            }
            if (nums[r] <= q) ++r;
            ll temp = prefix[n] - prefix[r] - (n - r) * (ll)q;
            temp += (ll)q * r - prefix[r] - prefix[0];
            res.push_back(temp);
        }
        return res;
    }
};

6356. 收集树中金币 ​

图的遍历 + 优先级队列。我们首先可以这样想，如果没有金币的结点和所在的分支都被剪去，并将所有包含金币的叶结点的结点去掉，并加上标记，这样的子图就是最优子图，而且这个子图是树，遍历整棵树再回到起点，这样的路径就是最优路径。而遍历整棵树的路径长度是 2(n−1)2(n - 1)，nn 结点的个数。

首先遍历边构建图，找出所有的叶结点（度为 11），然后加入到优先级队列，每次从优先级队列中取出一结点，然后将其结点的度减 11，如果结点的度变为 11，那么就加入到优先级队列中。这样每次都是取结点，这样就能保证每次都是取出最优结点。将金币到其结点的距离记为权重，如果权重大于 22，那么就记录这个路径，最后返回 2(n−1)2(n - 1) 即可。

cpp
class Solution {
public:
    int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) {
        int n = (int)coins.size();
        vector<vector<int>> graph(n);
        vector<int> degrees(n, 0);
        for (auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
            degrees[edge[0]]++;
            degrees[edge[1]]++;
        }
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        for (int i = 0; i < n; i++) {
            if (degrees[i] == 1) pq.push(make_pair(coins[i], i));
        }
        int res = 0;
        while (!pq.empty()) {
            auto p = pq.top();
            pq.pop();
            int node = p.second;
            if (coins[node] > 2) res++;
            for (int next : graph[node]) {
                if (coins[node] && degrees[next] > 1)
                    coins[next] = max(coins[next], coins[node] + 1);
                if (--degrees[next] == 1) pq.push(make_pair(coins[next], next));
            }
        }
        return max(0, (res - 1) * 2);
    }
};