2611. 老鼠和奶酪

2611. 老鼠和奶酪 (Medium)

有两只老鼠和 n 块不同类型的奶酪，每块奶酪都只能被其中一只老鼠吃掉。

下标为 i 处的奶酪被吃掉的得分为：

• 如果第一只老鼠吃掉，则得分为 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 块奶酪（下标从 0 开始），第二只老鼠不吃任何奶酪。
总得分为 1 + 1 = 2 。
2 是最高得分。

提示：

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

import “sort”

分析

非常有意思的一个问题。

可以这样思考：先让老鼠2吃光所有奶酪，然后老鼠1 吃 k 块（虽然全被老鼠2吃了，但可以假设能从其肚子里掏出来再吃~~）

这样一来就能算出总得分了。

老鼠2全吃，总得分很好算；接下来，老鼠1吃k块，假设吃的是第 i 块，那么总得分的变化值为 diff[i] = reword1[i]-reword2[2]

要使得最终得分最高，就需要 k 个 diff 的和最大。

所以可以先计算老鼠2吃光所有奶酪的总得分，再计算整个 diff 数组，再其中找出最大的 k 个 加上原得分即可。

func miceAndCheese(reward1 []int, reward2 []int, k int) int {
	n := len(reward1)
	diff := make([]int, n)
	sum2 := 0
	for i := 0; i < n; i++ {
		diff[i] = reward1[i] - reward2[i]
		sum2 += reward2[i]
	}

	sort.Ints(diff)
	for i := n - 1; i >= n-k; i-- {
		sum2 += diff[i]
	}

	return sum2
}

这里直接对 diff 做了排序，实际上可以用堆来优化，代码略。

时间复杂度 O(nlogn), 空间复杂度 O(n).

用堆优化可以将时间复杂度降为 O(nlogk).