老鼠和奶酪

Posted on Edited on In Views: Waline: Symbols count in article: 152 Reading time ≈ 1 mins.

题解方法

  • 贪心
  • 优先队列

贪心

  1. 假设 n 块奶酪都被第二只小鼠吃掉，记为 $sum$。
  2. 如果第 i 块奶酪被第一只小鼠吃掉，数值差值记为 $diff[i]$。
  3. 差值 $diff$ 降序排列，取前 k 个值与 $sum$ 相加即为结果。

优先队列

使用优先队列在一次遍历中维护 $diff$ 中前 k 个最大值。

会增加时间和空间的开销。

核心代码

1
2
3
4
5
6
7
8
for (int i = 0; i < reward1.length; i++) {  
	sum += reward2[i];  
	queue.add(reward1[i] - reward2[i]);  
	  
	if (queue.size() > k) {  
	queue.poll();  
	}  
}

题目来源