LeetCode 3767 选择 K 个任务的最大总分：贪心算法详解

LeetCode 3767 选择 K 个任务的最大总分

本题是一道贪心算法题目，难度中等。本文按照完整的思考逻辑进行解析，从初步思路到最终优化方案。

题目描述

给定两个整数数组 technique1 和 technique2，以及一个整数 k。

• 如果第 i 个任务使用技巧 1 完成，获得 technique1[i] 分。
• 如果使用技巧 2 完成，获得 technique2[i] 分。
• 必须使用技巧 1 完成 至少 k 个任务。

求能获得的最大总分。

思路分析

前置分析

贪心算法的核心思想是局部最优造就全局最优。想要获得最大的总分，通常希望每次做任务时获得的分数最大。即对于每个任务，优先选择 max(technique1[i], technique2[i])。

但题目限制必须使用技巧 1 至少 k 次。这导致不能简单地每次都选最大值。

初步考虑

若强制前 k 个任务使用技巧 1，剩余任务选最大值，这种策略并不一定最优。因为前 k 个最大的 technique1 对应的 technique2 可能更大，或者某些 technique1 较小但 technique2 更小的组合更优。

深入分析

我们需要权衡使用技巧 1 带来的收益变化。定义差值 diff[i] = technique1[i] - technique2[i]。

• 若 diff[i] > 0，说明用技巧 1 比技巧 2 多得分。
• 若 diff[i] < 0，说明用技巧 1 比技巧 2 少得分。

策略如下：

1. 假设所有任务都先使用技巧 2，计算基础总分。
2. 计算所有任务的 diff 值并降序排序。
3. 优先选择 diff 为正的任务切换为技巧 1（增加总分）。
4. 若正 diff 数量不足 k，则继续选取 diff 最大的负数任务切换为技巧 1，以满足至少 k 次的约束。

疑惑解释

若有多个任务 diff 相同，无论选哪个，对总分的影响一致。例如 diff 均为 -3，选哪个任务切换为技巧 1，总分减少量都是 3，因此不影响最终结果的最优性。

代码实现

基于上述简化思路，我们可以先累加所有 technique2 的值，再根据排序后的 diff 数组调整总分。

class Solution {
private:
    static bool cmp(int x, int y) {
        return x > y;
    }
public:
    long long maxPoints(vector<int>& technique1, vector<int>& technique2, int k) {
        int n = technique1.size();
        vector<int> diff(n);
        long long ans = 0;
        for (int i = 0; i < n; ++i) {
            diff[i] = technique1[i] - technique2[i];
            ans += technique2[i];
        }
        sort(diff.begin(), diff.end(), cmp);
        
        int posCount = 0;
        // 优先加上所有正差值
        for (int i = 0; i < n && diff[i] > 0; ++i) {
            ans += diff[i];
            ++posCount;
        }
        
        // 如果正差值数量不足 k，继续补充直到满足 k 次
        if (posCount < k) {
            for (int i = posCount; i < k; ++i) {
                ans += diff[i];
            }
        }
        return ans;
    }
};

总结

本题关键在于将问题转化为差值排序问题。通过固定基准（全技巧 2），利用差值大小决定切换次数，既满足了数量约束，又保证了总分最大化。