Medium

题目描述

给你两个整数数组 technique1 和 technique2，每个数组的长度都是 n，其中 n 表示要完成的任务数量。

  • 如果第 i 个任务使用技术1完成，你将获得 technique1[i] 分。
  • 如果使用技术2完成，你将获得 technique2[i] 分。

同时给你一个整数 k，表示必须使用技术1完成的最少任务数量。

你必须至少使用技术1完成 k 个任务（它们不需要是前 k 个任务）。

剩余的任务可以使用任一技术完成。

返回你能获得的最大总积分。

示例 1：

输入：technique1 = [5,2,10], technique2 = [10,3,8], k = 2
输出：22
解释：我们必须至少使用技术1完成 k = 2 个任务。
选择 technique1[1] 和 technique1[2]（使用技术1完成），以及 technique2[0]（使用技术2完成），获得最大积分：2 + 10 + 10 = 22。

示例 2：

输入：technique1 = [10,20,30], technique2 = [5,15,25], k = 2
输出：60
解释：我们必须至少使用技术1完成 k = 2 个任务。
选择所有任务都使用技术1完成，获得最大积分：10 + 20 + 30 = 60。

示例 3：

输入：technique1 = [1,2,3], technique2 = [4,5,6], k = 0
输出：15
解释：由于 k = 0，我们不需要选择任何任务使用技术1。
选择所有任务都使用技术2完成，获得最大积分：4 + 5 + 6 = 15。

约束条件：

  • 1 <= n == technique1.length == technique2.length <= 10^5
  • 1 <= technique1[i], technique2[i] <= 10^5
  • 0 <= k <= n

解题思路

这道题的核心思路是贪心算法。我们需要在满足至少使用技术1完成k个任务的前提下，最大化总积分。

基本思路：

  1. 首先假设所有任务都使用技术1完成，计算初始总积分
  2. 计算每个任务从技术1切换到技术2的收益差值：delta[i] = technique2[i] - technique1[i]
  3. 将收益差值按降序排序
  4. 由于必须至少使用技术1完成k个任务，所以最多只能有n-k个任务切换到技术2
  5. 贪心地选择收益差值最大的前n-k个任务切换到技术2

优化策略： 为了处理可能的边界情况，我们可以枚举使用技术1的任务数量从k到n，对于每种情况计算最大积分：

  • 当使用技术1完成exactly j个任务时，剩余n-j个任务使用技术2
  • 选择收益差值最大的n-j个任务切换到技术2
  • 在所有可能的j值中选择最大积分

这种方法确保我们能找到全局最优解，时间复杂度为O(n log n)，主要消耗在排序上。

代码实现

class Solution {
public:
    long long maxPoints(vector<int>& technique1, vector<int>& technique2, int k) {
        int n = technique1.size();
        vector<int> delta(n);
        long long sum1 = 0;
        
        for (int i = 0; i < n; i++) {
            delta[i] = technique2[i] - technique1[i];
            sum1 += technique1[i];
        }
        
        sort(delta.begin(), delta.end(), greater<int>());
        
        long long maxPoints = sum1;
        long long currentSum = sum1;
        
        for (int i = 0; i < n - k; i++) {
            currentSum += delta[i];
            maxPoints = max(maxPoints, currentSum);
        }
        
        return maxPoints;
    }
};

class Solution:
    def maxPoints(self, technique1: List[int], technique2: List[int], k: int) -> int:
        n = len(technique1)
        delta = [technique2[i] - technique1[i] for i in range(n)]
        sum1 = sum(technique1)
        
        delta.sort(reverse=True)
        
        max_points = sum1
        current_sum = sum1
        
        for i in range(n - k):
            current_sum += delta[i]
            max_points = max(max_points, current_sum)
        
        return max_points

public class Solution {
    public long MaxPoints(int[] technique1, int[] technique2, int k) {
        int n = technique1.Length;
        int[] delta = new int[n];
        long sum1 = 0;
        
        for (int i = 0; i < n; i++) {
            delta[i] = technique2[i] - technique1[i];
            sum1 += technique1[i];
        }
        
        Array.Sort(delta, (a, b) => b.CompareTo(a));
        
        long maxPoints = sum1;
        long currentSum = sum1;
        
        for (int i = 0; i < n - k; i++) {
            currentSum += delta[i];
            maxPoints = Math.Max(maxPoints, currentSum);
        }
        
        return maxPoints;
    }
}

var maxPoints = function(technique1, technique2, k) {
    const n = technique1.length;
    const delta = [];
    let sum1 = 0;
    
    for (let i = 0; i < n; i++) {
        delta[i] = technique2[i] - technique1[i];
        sum1 += technique1[i];
    }
    
    delta.sort((a, b) => b - a);
    
    let maxPoints = sum1;
    let currentSum = sum1;
    
    for (let i = 0; i < n - k; i++) {
        currentSum += delta[i];
        maxPoints = Math.max(maxPoints, currentSum);
    }
    
    return maxPoints;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n log n)主要消耗在对收益差值数组的排序上
空间复杂度O(n)需要额外空间存储收益差值数组