题目 #

There are two mice and n different types of cheese, each type of cheese should be eaten by exactly one mouse.

A point of the cheese with index i (0-indexed) is:

• reward1[i] if the first mouse eats it.
• reward2[i] if the second mouse eats it.

You are given a positive integer array reward1, a positive integer array reward2, and a non-negative integer k.

Return the maximum points the mice can achieve if the first mouse eats exactly k types of cheese.

Example 1:

Input: reward1 = [1,1,3,4], reward2 = [4,4,1,1], k = 2
Output: 15
Explanation: In this example, the first mouse eats the 2nd (0-indexed) and the 3rd types of cheese, and the second mouse eats the 0th and the 1st types of cheese.
The total points are 4 + 4 + 3 + 4 = 15.
It can be proven that 15 is the maximum total points that the mice can achieve.

Example 2:

Input: reward1 = [1,1], reward2 = [1,1], k = 2
Output: 2
Explanation: In this example, the first mouse eats the 0th (0-indexed) and 1st types of cheese, and the second mouse does not eat any cheese.
The total points are 1 + 1 = 2.
It can be proven that 2 is the maximum total points that the mice can achieve.

Constraints:

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

思路1 贪心 #

分析 #

• 先全部给第二只老鼠吃，然后选k个给第一个老鼠吃
• 选的都是收益最大化的k个，那么就把差异排个序，取最大的k个

代码 #

 1func miceAndCheese(reward1 []int, reward2 []int, k int) int {
 2	res := 0
 3	n := len(reward1)
 4	diff := make([]int, n)
 5	// 全部让老鼠2吃
 6	for i, v := range reward2 {
 7		res += v
 8		diff[i] = reward1[i] - reward2[i]
 9	}
10	sort.Ints(diff)
11	for i := 0; i < k; i++ {
12		res += diff[n-1-i]
13	}
14	return res
15}