本题练习地址：https://oj.algomooc.com/
一、题目描述与示例
歌手准备从 A 城去 B 城参加演出
- 按照合同，他必须在
T天内赶到。 - 歌手途径
N座城市。 - 歌手不能往回走。
- 每两座城市之间需要的天数都可以提前获知。
- 歌手在每座城市都可以在路边卖唱赚钱。经过调研，歌手提前获知了每座城市卖唱的收入预期。如果在一座城市第一天卖唱可以赚
M，后续每天的收入会减少D(第二天赚的钱是M-D，第三天是M-2D…)。如果收入减到0就不会再少了。 - 歌手到达后的第二天才能开始卖唱。如果今天卖过唱，第二天才能出发。
问贪心的歌手最多可以赚多少钱？
输入描述
第一行两个数字 T 和 N，中间用空格隔开，T 代表总天数； N 代表路上经过 N 座城市;
0 < T < 1000，0 < N < 100
第二行 N 1 个数字，中间用空格隔开，代表每两座城市之间耗费的时间，其总和<=T。
接下来 N 行，每行两个数字 M 和 D，中间用空格隔开。代表每个城市的收入预期。
0 < M < 1000，0 < D < 100
输出描述
一个数字。代表歌手最多可以赚多少钱。以回车结束
示例一
输入
代码语言：javascript复制10 2
1 1 2
120 20
90 10
输出
代码语言：javascript复制540
说明
总共 10 天，路上经过 2 座城市。 路上共花 1 1 2=4 天。 剩余 6 天最好的计划是在第一座城市待 3 天，在第二座城市待 3 天。 在第一座城市赚的钱：120 100 80 = 300 在第二座城市赚的钱：90 80 70 = 240
共 300 240 = 540
示例二
输入
代码语言：javascript复制10 3
1 1 2 3
120 20
90 10
100 20
输出
代码语言：javascript复制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 = 50M2 < M1，在第二个城市进行卖唱，赚的钱ans = 100 80，在第二个城市赚到的钱衰减为M2 = 80 - 40 = 40M1 < M2，在第一个城市进行卖唱，赚的钱ans = 100 80 50，在第一个城市赚到的钱衰减为M1 = 50 - 50 = 0
那么X = 3就用完了，最多可以赚ans = 100 80 50 = 230。
虽然真正的时间线为1(两天) -> 2(一天)，但是分析问题时我们的过程是1(一天) -> 2(一天) -> 1(一天)，但也能够计算出正确的答案。
上述过程涉及到动态维护最大值的情形，很显然可以使用优先队列来维护该过程。具体过程如下：
- 构建一个以最大值为排序依据的优先队列（即大根堆）
heap - 将每一个城市的
(M, D)储存在堆中。 - 循环
X次，表示最多可以停留X天在进行卖唱。- 弹出堆顶元素
M, D，此时可以赚到M，即更新ans = M - 计算衰减后该城市能够赚到的钱
M -= D。 - 如果
M衰减了D之后，仍大于0，说明还有可能继续在这个城市赚钱，需要将(M, D)重新入堆
- 弹出堆顶元素
- 注意在循环中，必须判断
heap的长度是否大于0。如果等于0，说明优先队列中无元素，所有的城市赚的钱都衰减到0了，此时可以直接退出循环。
不熟悉优先队列的同学，每一次最大值挑选完衰减后再次插入原数组的操作，也可以直接用排序的API来完成。由于插入完毕后至多只有一个元素是无序的，加上
N的最大值只有100，因此这里直接使用排序并不会比优先队列慢很多。
三、代码
Python
代码语言：javascript复制# # 题目：【贪心】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
代码语言：javascript复制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 < N 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 < N; 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 < X; 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
代码语言：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', () => {
let [T, N] = input[0].split(' ').map(Number);
let days = input[1].split(' ').map(Number);
let heap = new PriorityQueue((a, b) => a[0] - b[0]); // Max heap
for (let i = 0; i < N; i ) {
let [M, D] = input[i 2].split(' ').map(Number);
heap.offer([M, D]);
}
let X = T - days.reduce((a, b) => a b, 0);
let ans = 0;
for (let i = 0; i < X; i ) {
if (heap.isEmpty()) break;
let city = heap.poll();
let [M, D] = city;
ans = M;
M -= D;
if (M > 0) heap.offer([M, D]);
}
console.log(ans);
});
class PriorityQueue {
constructor(comparator) {
this.comparator = comparator;
this.heap = [];
}
offer(val) {
this.heap.push(val);
this.bubbleUp(this.heap.length - 1);
}
poll() {
if (!this.isEmpty()) {
let len = this.heap.length;
this.swap(0, len - 1);
let val = this.heap.pop();
this.bubbleDown(0);
return val;
}
}
isEmpty() {
return this.heap.length === 0;
}
bubbleUp(idx) {
while (idx > 0) {
let parent = Math.floor((idx - 1) / 2);
if (this.comparator(this.heap[idx], this.heap[parent]) > 0) {
this.swap(idx, parent);
idx = parent;
} else {
break;
}
}
}
bubbleDown(idx) {
let len = this.heap.length;
while (idx < len) {
let leftChild = idx * 2 1;
let rightChild = idx * 2 2;
let largest = idx;
if (leftChild < len && this.comparator(this.heap[leftChild], this.heap[largest]) > 0) {
largest = leftChild;
}
if (rightChild < len && this.comparator(this.heap[rightChild], this.heap[largest]) > 0) {
largest = rightChild;
}
if (largest !== idx) {
this.swap(idx, largest);
idx = largest;
} else {
break;
}
}
}
swap(i, j) {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
}
C
代码语言：javascript复制#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
int T, N;
cin >> T >> N;
vector<int> days(N 1);
for (int i = 0; i < N 1; i ) {
cin >> days[i];
}
priority_queue<pair<int, int>> heap; // Max heap
for (int i = 0; i < N; i ) {
int M, D;
cin >> M >> D;
heap.push({M, D});
}
int X = T;
for (int i = 0; i < N 1; i ) {
X -= days[i];
}
int ans = 0;
for (int i = 0; i < X; i ) {
if (heap.empty()) {
break;
}
auto city = heap.top();
heap.pop();
int M = city.first;
int D = city.second;
ans = M;
M -= D;
if (M > 0) {
heap.push({M, D});
}
}
cout << ans << endl;
return 0;
}
时空复杂度
时间复杂度：O(XlogN)。优先队列单次插入操作的时间复杂度为O(logN)
空间复杂度：O(N)。优先队列最多时储存N个元素。
