本题练习地址：https://oj.algomooc.com/
一、题目描述与示例
歌手准备从 A 城去 B 城参加演出
-
-
-
-
-
歌手在每座城市都可以在路边卖唱赚钱。经过调研，歌手提前获知了每座城市卖唱的收入预期。如果在一座城市第一天卖唱可以赚
M
，后续每天的收入会减少
D
(第二天赚的钱是
M-D
，第三天是
M-2D
…)。如果收入减到
0
就不会再少了。
-
歌手到达后的第二天才能开始卖唱。如果今天卖过唱，第二天才能出发。
问贪心的歌手最多可以赚多少钱？
输入描述
第一行两个数字
T
和
N
，中间用空格隔开，
T
代表总天数；
N
代表路上经过
N
座城市;
0
第二行
N+1
个数字，中间用空格隔开，代表每两座城市之间耗费的时间，其总和
<=T
。
接下来
N
行，每行两个数字
M
和
D
，中间用空格隔开。代表每个城市的收入预期。
0
输出描述
一个数字。代表歌手最多可以赚多少钱。以回车结束
示例一
输入
10 2
1 1 2
120 20
90 10
输出
540
说明
总共
10
天，路上经过
2
座城市。 路上共花
1+1+2=4
天。 剩余
6
天最好的计划是在第一座城市待
3
天，在第二座城市待
3
天。 在第一座城市赚的钱：
120 + 100 + 80 = 300
在第二座城市赚的钱：
90 + 80 + 70 = 240
共
300 +240 = 540
示例二
输入
10 3
1 1 2 3
120 20
90 10
100 20
输出
320
二、解题思路
题目的名字已经把这道题用的算法告诉你了——
贪心
。
题干非常长，得好好理解题意。
首先歌手能够卖唱的所有天数是固定的。假设总时间为
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
-
M2 < M1
，在第二个城市进行卖唱，赚的钱
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(一天)
，但也能够计算出正确的答案。
上述过程涉及到动态维护最大值的情形，很显然可以使用
优先队列来维护该过程
。具体过程如下：
-
构建一个以最大值为排序依据的优先队列（即大根堆）
heap
-
-
循环
X
次，表示最多可以停留
X
天在进行卖唱。
-
弹出堆顶元素
M, D
，此时可以赚到
M
，即更新
ans += M
-
-
如果
M
衰减了
D
之后，仍大于
0
，说明还有可能继续在这个城市赚钱，需要将
(M, D)
重新入堆
-
注意在循环中，必须判断
heap
的长度是否大于
0
。如果等于
0
，说明优先队列中无元素，所有的城市赚的钱都衰减到
0
了，此时可以直接退出循环。
不熟悉优先队列的同学，每一次最大值挑选完衰减后再次插入原数组的操作，也可以直接用排序的API来完成。由于插入完毕后至多只有一个元素是无序的，加上
N
的最大值只有
100
，因此这里直接使用排序并不会比优先队列慢很多。
三、代码
Python
# # 题目：【贪心】2023C-贪心歌手
# # 分值：200
# # 作者：闭着眼睛学数理化
# # 算法：贪心，优先队列
# # 代码看不懂的地方，请直接在群上提问
from heapq import heappush, heappop
# 总天数，城市数
T, N = map(int, input().split())
# 路程天数
days = list(map(int, input().split()))
# 初始化一个大根堆
heap = list()
# N个城市的初始金额M和衰减速度D
for _ in range(N):
M, D = map(int, input().split())
# 将(M, D)入堆，
# 由于维护的是大根堆，所以储存的是(-M, D)
heappush(heap, (-M, D))
# 可以卖唱的总天数X
X = T - sum(days)
ans = 0
# 遍历X天
for i in range(X):
# 如果堆中无元素，则说明所有的城市赚的钱都衰减到0了
# 直接退出循环
if len(heap) == 0:
break
# 弹出堆中绝对值最大的M
M, D = heappop(heap)
# 之前储存的M是负数，改为正数
M = -M
# 选择在这个城市卖唱，可以赚到M
ans += M
# 赚完了M，需要衰减D，更新M的值
M -= D
# 如果M衰减了D之后，仍大于0，说明还有可能继续在这里赚钱，重新入堆
if M > 0:
heappush(heap, (-M, D))
print(ans)
Java
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int T = scanner.nextInt();
int N = scanner.nextInt();
int[] days = new int[N+1];
for (int i = 0; i 1; i++) {
days[i] = scanner.nextInt();
}
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0])); // Max heap
for (int i = 0; i int M = scanner.nextInt();
int D = scanner.nextInt();
heap.offer(new int[]{M, D});
}
int X = T - sum(days);
int ans = 0;
for (int i = 0; i if (heap.isEmpty()) {
break;
}
int[] city = heap.poll();
int M = city[0];
int D = city[1];
ans += M;
M -= D;
if (M > 0) {
heap.offer(new int[]{M, D});
}
}
System.out.println(ans);
}
private static int sum(int[] arr) {
int sum = 0;
for (int num : arr) {
sum += num;
}
return sum;
}
}
JavaScript
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
let input = [];
rl.on('line', line => {
input.push(line);
}).on('close'
