老鼠和奶酪

Posted on Edited on In Views: Waline: Views: Symbols count in article: 324 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();  
    	}  
    }

    题目来源