Medium

题目描述

有两只老鼠和 n 块不同类型的奶酪，每块奶酪都应该被恰好一只老鼠吃掉。

索引为 i（从 0 开始）的奶酪被吃掉的得分为：

  • 如果第一只老鼠吃掉，得分为 reward1[i]
  • 如果第二只老鼠吃掉，得分为 reward2[i]

给你一个正整数数组 reward1，一个正整数数组 reward2，和一个非负整数 k。

请你返回在第一只老鼠恰好吃掉 k 块奶酪的前提下，两只老鼠能够获得的最大得分。

示例 1：

输入：reward1 = [1,1,3,4], reward2 = [4,4,1,1], k = 2
输出：15
解释：第一只老鼠吃第 2 和第 3 块奶酪（从 0 开始索引），第二只老鼠吃第 0 和第 1 块奶酪。
总得分为 4 + 4 + 3 + 4 = 15。
可以证明 15 是两只老鼠能够获得的最大总得分。

示例 2：

输入：reward1 = [1,1], reward2 = [1,1], k = 2
输出：2
解释：第一只老鼠吃第 0 和第 1 块奶酪，第二只老鼠不吃任何奶酪。
总得分为 1 + 1 = 2。
可以证明 2 是两只老鼠能够获得的最大总得分。

提示：

  • 1 <= n == reward1.length == reward2.length <= 10^5
  • 1 <= reward1[i], reward2[i] <= 1000
  • 0 <= k <= n

解题思路

这是一个贪心算法问题。关键在于理解收益的最大化策略。

基本思路： 我们可以换个角度思考这个问题。假设最初所有奶酪都由第二只老鼠吃掉，总得分为所有 reward2[i] 的和。现在我们需要选择 k 块奶酪改为第一只老鼠吃，这样会带来得分的变化。

贪心策略： 对于每块奶酪 i，如果从第二只老鼠改为第一只老鼠吃，得分变化为：reward1[i] - reward2[i]。为了最大化总得分，我们应该选择得分变化最大的 k 块奶酪给第一只老鼠吃。

算法步骤：

  1. 计算每块奶酪的得分差值：diff[i] = reward1[i] - reward2[i]
  2. 将差值按降序排序
  3. 选择前 k 个最大差值的奶酪给第一只老鼠
  4. 总得分 = 所有 reward2 的和 + 前 k 个最大差值的和

这种方法的时间复杂度为 O(n log n)，空间复杂度为 O(n)。

代码实现

class Solution {
public:
    int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {
        int n = reward1.size();
        vector<pair<int, int>> diff;
        int totalReward2 = 0;
        
        for (int i = 0; i < n; i++) {
            diff.push_back({reward1[i] - reward2[i], i});
            totalReward2 += reward2[i];
        }
        
        sort(diff.begin(), diff.end(), greater<pair<int, int>>());
        
        int result = totalReward2;
        for (int i = 0; i < k; i++) {
            result += diff[i].first;
        }
        
        return result;
    }
};

class Solution:
    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:
        n = len(reward1)
        diff = []
        total_reward2 = sum(reward2)
        
        for i in range(n):
            diff.append(reward1[i] - reward2[i])
        
        diff.sort(reverse=True)
        
        result = total_reward2 + sum(diff[:k])
        return result

public class Solution {
    public int MiceAndCheese(int[] reward1, int[] reward2, int k) {
        int n = reward1.Length;
        int[] diff = new int[n];
        int totalReward2 = 0;
        
        for (int i = 0; i < n; i++) {
            diff[i] = reward1[i] - reward2[i];
            totalReward2 += reward2[i];
        }
        
        Array.Sort(diff, (a, b) => b.CompareTo(a));
        
        int result = totalReward2;
        for (int i = 0; i < k; i++) {
            result += diff[i];
        }
        
        return result;
    }
}

var miceAndCheese = function(reward1, reward2, k) {
    const n = reward1.length;
    const diff = [];
    let totalReward2 = 0;
    
    for (let i = 0; i < n; i++) {
        diff.push(reward1[i] - reward2[i]);
        totalReward2 += reward2[i];
    }
    
    diff.sort((a, b) => b - a);
    
    let result = totalReward2;
    for (let i = 0; i < k; i++) {
        result += diff[i];
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

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

相关题目