P3131. 贪心歌手

解题思路

题目的名字已经把这道题用的算法告诉你了——贪心。

题干非常长，得好好理解题意。

首先歌手能够卖唱的所有天数是固定的。假设总时间为 T，花费在路上的时间数组为 days，那么可以停下来卖唱的时间为 X = T - sum(days)。这是很容易分析出来的结论。

那么为了能够赚更多的钱，我们一定要把 X 天都拉满，即尽可能地停留在某个城市赚钱。

这 X 天的分配实际上是任意的，停留在哪一个城市都行，只要停留够 X 天就肯定能赚到尽可能多的钱。实际上我们并不需要按照歌手的时间线来考虑问题，而是按照某一天能够在哪个城市获得的钱数最多来考虑问题的。

例子分析

考虑例子： 停留的卖唱天数 X = 3，第一个城市的起始金额 M1 = 100，衰减速度 D1 = 50，第二个城市的起始金额 M2 = 80，衰减速度 D1 = 40。我们会做如下分析：

• M1 > M2，在第一个城市进行卖唱，赚的钱 ans = 100，在第一个城市赚到的钱衰减为 M1 = 100 - 50 = 50
• M1 < M2，在第二个城市进行卖唱，赚的钱 ans = 100 + 80，在第二个城市赚到的钱衰减为 M2 = 80 - 40 = 40
• M1 < M2，在第一个城市进行卖唱，赚的钱 ans = 100 + 80 + 50，在第一个城市赚到的钱衰减为 M1 = 50 - 50 = 0

那么 X = 3 就用完了，最多可以赚 ans = 100 + 80 + 50 = 230。

虽然真正的时间线为 1(两天) -> 2(一天)，但是分析问题时我们的过程是 1(一天) -> 2(一天) -> 1(一天)，但也能够计算出正确的答案。

使用优先队列

上述过程涉及到动态维护最大值的情形，很显然可以使用优先队列来维护该过程。具体过程如下：

1. 构建一个以最大值为排序依据的优先队列（即大根堆）heap 2. 将每一个城市的 (M, D) 储存在堆中。 3. 循环 X 次，表示最多可以停留 X 天在进行卖唱。

• 弹出堆顶元素 M, D，此时可以赚到 M，即更新 ans += M
• 计算衰减后该城市能够赚到的钱 M -= D
• 如果 M 衰减了 D 之后，仍大于 0，说明还有可能继续在这个城市赚钱，需要将 (M, D) 重新入堆

4. 注意在循环中，必须判断 heap 的长度是否大于 0。如果等于 0，说明优先队列中无元素，所有的城市赚的钱都衰减到 0 了，此时可以直接退出循环。

替代方案

不熟悉优先队列的同学，每一次最大值挑选完衰减后再次插入原数组的操作，也可以直接用排序的 API 来完成。由于插入完毕后至多只有一个元素是无序的，加上 N 的最大值只有 100，因此这里直接使用排序并不会比优先队列慢很多。

复杂度分析 设 N 为城市数，X = T - sum(days) 为扣除路程后可用来卖唱的总天数。

• 时间复杂度：O(N log N + X log N)。建堆阶段把 N 个城市的 (M, D) 依次入堆，共 O(N log N)；主循环最多执行 X 轮，每轮一次 heappop 取出当前收入最高的城市，加上至多一次 heappush 把衰减后仍大于 0 的 (M, D) 放回堆中，单轮为 O(log N)。若所有城市的收入都衰减到 0，堆会提前变空并退出循环，只会更快。
• 空间复杂度：O(N)，主要是储存各城市 (M, D) 的优先队列，堆中元素个数始终不超过 N，另有路程数组 days 的 O(N)。