2611. 老鼠和奶酪

题目描述

有两只老鼠和 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

解法一：贪心 + 排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


func miceAndCheese(reward1 []int, reward2 []int, k int) int {
    n := len(reward1)
    diff := make([][2]int, n)
    for i := 0; i < n; i++ {
        diff[i] = [2]int{reward2[i] - reward1[i], i}
    }
    sort.Slice(diff, func(i, j int) bool {
        return diff[i][0] < diff[j][0]
    })
    res := 0
    for i := 0; i < k; i++ {
        idx := diff[i][1]
        res += reward1[idx]
        reward2[idx] = 0
    }
    for _, val := range reward2 {
        res += val
    }
    return res
}

官方题解如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


func miceAndCheese(reward1 []int, reward2 []int, k int) int {
    ans := 0
    n := len(reward1)
    diffs := make([]int, n)
    for i:= 0; i < n; i++ {
        ans += reward2[i]
        diffs[i] = reward1[i] - reward2[i]
    }
    sort.Ints(diffs)
    for i:=1; i <= k; i++ {
        ans += diffs[n - i]
    }
    return ans
}

解法二：贪心 + 优先队列

官方题解如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


type IntHeap []int

func (h IntHeap) Less(i, j int) bool {
    return h[i] < h[j]
}
func (h IntHeap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}
func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}
func (h IntHeap) Len() int {
    return len(h)
}
func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n - 1]
    *h = old[:n - 1]
    return x
}

func miceAndCheese(reward1 []int, reward2 []int, k int) int {
    ans := 0
    n := len(reward1)
    pq := &IntHeap{}
    heap.Init(pq)
    for i := 0; i < n; i++ {
        ans += reward2[i]
        diff := reward1[i] - reward2[i]
        heap.Push(pq, diff)
        if pq.Len() > k {
            heap.Pop(pq)
        }
    }
    for pq.Len() > 0 {
        ans += heap.Pop(pq).(int)
    }
    return ans
}