题目描述

一个歌手准备从A城去B城参加演出。

1. 按照合同，他必须在 T 天内赶到
2. 歌手途经 N 座城市
3. 歌手不能往回走
4. 每两座城市之间需要的天数都可以提前获知。
5. 歌手在每座城市都可以在路边卖唱赚钱。
   经过调研，歌手提前获知了每座城市卖唱的收入预期： 如果在一座城市第一天卖唱可以赚M，后续每天的收入会减少D（第二天赚的钱是 M - D，第三天是 M - 2D …）。如果收入减少到 0 就不会再少了。
6. 歌手到达后的第二天才能开始卖唱。如果今天卖过唱，第二天才能出发。
   贪心的歌手最多可以赚多少钱

输入描述
第一行两个数字 T 和 N，中间用空格隔开。

• T 代表总天数，0 < T < 1000
• N 代表路上经过 N 座城市，0 < N < 100

第二行 N+1 个数字，中间用空格隔开。代表每两座城市之间耗费的时间。

• 其总和 ≤ T。

接下来 N 行，每行两个数字 M 和 D，中间用空格隔开。代表每个城市的收入预期。

• 0 < M < 1000
• 0 < D < 100

用例
输入

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。

思考

先计算除去路上花费的天数后剩余可分配天数，在 N 个城市中按顺序卖唱的最大收益。用例中的数据，城市1的日收益如下：
120 100 80 60 40 20，城市2 的日收益： 90 80 70 60 50 40，假如剩余天数是6天，都在第一座城市卖唱，那么收益数组为：
[120,100,80,60,40,20]，显然后3天的收益 [60,40,20] 小于第二座城市前3天的收益 [90,80,70]，那么最大收益就是第一座城市停留3天收益+第二座城市停留3天的收益，即[120,100,80,90,80,70]。具体算法应该是先按顺序遍历每座经过的城市，对每个城市，假设剩余天数都停留在这座城市，得到一个收益列表 profits；下一轮循环遍历下一座城市时重复之前操作，但把收益列表中最小的收益数替换为当前更大的收益，这样最终的收益列表profits尽可能包含了每座城市中最大的收益数，即是整个歌手能获得的最大卖唱收益。可以用优先队列快速获取最小收益，并将较大收益数入队，优化时间复杂度。有些编程语言没有内置优先队列，不熟悉实现起来比较耗费时间，比如JavaScript，可以用数组模拟下，如：let minIndex = queue.lastIndexOf(Math.min(...queue)), queue[minIndex] = curElem;，只要做题时能通过就行。

算法过程

该算法基于最小优先队列（Min-Heap） 实现，核心思路是：从所有城市的可能卖唱日收益中，筛选出最大的leftDays个收益（leftDays为可用于卖唱的剩余天数），总和即为最大总收益。具体步骤如下：

步骤1：计算可用于卖唱的剩余天数

• 首先计算总路程耗时：将输入的N+1段路程时间求和（记为totalRoadDays）。
• 剩余可卖唱天数为：leftDays = T - totalRoadDays。若leftDays ≤ 0，则无时间卖唱，直接返回0。

步骤2：初始化最小优先队列

• 使用最小优先队列（堆）存储当前筛选出的最大日收益，队列最多容纳leftDays个元素（因为总共有leftDays天可卖唱）。
• 最小优先队列的特性是：顶部元素始终是当前队列中最小的元素，便于快速替换为更大的收益。

步骤3：遍历所有城市，计算并筛选日收益

对于每座城市，按顺序计算在该城市停留第1天、第2天……直到第leftDays天的日收益（超过leftDays天的收益无需计算，因为总天数有限），并按规则加入队列：

• 日收益计算规则：第j天（j从1开始）的收益为 max(M - D*(j-1), 0)（M为初始收益，D为每日递减值，收益不能为负）。
• 队列操作规则：
  • 若队列元素数量 < leftDays：直接将当前日收益加入队列（此时需要填充所有可能的天数）。
  • 若队列已满（元素数量 = leftDays）：比较当前日收益与队列顶部的最小收益。若当前收益更大，则移除队列中最小的收益，将当前收益加入队列（保证队列始终保留目前最大的leftDays个收益）。

步骤4：计算最大总收益

当所有城市的所有可能日收益都处理完毕后，队列中存储的是最大的leftDays个日收益。将这些收益求和，即为歌手能获得的最大总收益。

示例验证（对应题目用例）

1. 计算剩余天数：总天数T=10，路程时间1+1+2=4，故leftDays=6。
2. 处理第一座城市（M=120，D=20）：
   • 日收益依次为：120（第1天）、100（第2天）、80（第3天）、60（第4天）、40（第5天）、20（第6天）。
   • 队列初始为空，依次加入这6个收益，队列元素为[20,40,80,60,100,120]（堆顶为最小元素20）。
3. 处理第二座城市（M=90，D=10）：
   • 日收益依次为：90（第1天）、80（第2天）、70（第3天）、60（第4天）、50（第5天）、40（第6天）。
   • 逐个处理：
     • 90 > 堆顶20 → 移除20，加入90 → 队列元素更新（堆顶40）。
     • 80 > 堆顶40 → 移除40，加入80 → 队列元素更新（堆顶60）。
     • 70 > 堆顶60 → 移除60，加入70 → 队列元素更新（堆顶70）。
     • 60、50、40均小于堆顶70 → 不加入队列。
4. 求和队列元素：最终队列元素为70,80,80,90,100,120，总和为70+80+80+90+100+120=540，与用例结果一致。

算法核心逻辑

通过最小优先队列动态维护最大的leftDays个日收益，利用每个城市日收益单调递减的特性（每天收益≤前一天），确保筛选出的收益是全局最优的。该方法时间复杂度为O(N×leftDays×log(leftDays))，高效适用于题目约束（N<100，leftDays<T<1000）。

参考代码

class MinPriorityQueue {constructor() {this._data = [];}enqueue(e) {this._data.push(e);this.swim();}dequeue() {this._data.shift();if (this.isEmpty()) return;let lastElem = this._data.pop();this._data.unshift(lastElem);this.sink();}swim() {const n = this._data.length;let index = n - 1;while (index > 0) {let parentIndex = Math.floor((index-1)/2);if (this._data[index] < this._data[parentIndex]) {[this._data[parentIndex], this._data[index]] = [this._data[index], this._data[parentIndex]];index = parentIndex;continue;}break;}}sink() {let index = 0;const n = this._data.length;while (true) {let left = 2 * index + 1;let right = left + 1;let smallest = index;if (left < n && this._data[left] < this._data[index]) {smallest = left;}if (right < n && this._data[right] < this._data[smallest]) {smallest = right;}if (smallest !== index) {[this._data[smallest], this._data[index]] = [this._data[index], this._data[smallest]];index = smallest;continue;}break;}}top() {return this._data[0];}isEmpty() {return this._data.length === 0;}size() {return this._data.length;}
}function solution() {const [T, N] = readline().split(' ').map(Number);const times = readline().split(' ').map(Number);const cities = [];for (let i = 0; i < N; i++) {cities[i] = readline().split(' ').map(Number);}const leftDaysNum = T - times.reduce((cur,acc) => cur + acc);const profits = new MinPriorityQueue();for (let i = 0; i < N; i++) {for (let j = 0; j < leftDaysNum; j++) {let curProfit = Math.max(cities[i][0] - cities[i][1] * j, 0);if (curProfit === 0) {break;}if (profits.size() < leftDaysNum) {profits.enqueue(curProfit);} else {if (curProfit > profits.top()) {profits.dequeue();profits.enqueue(curProfit);}}}}let result = 0;while (profits.size()) {result += profits.top();profits.dequeue();}console.log(result);
}const cases = [`10 2
1 1 2
120 20
90 10`,
];let caseIndex = 0;
let lineIndex = 0;const readline = (function () {let lines = [];return function () {if (lineIndex === 0) {lines = cases[caseIndex].trim().split("\n").map((line) => line.trim());}return lines[lineIndex++];};
})();cases.forEach((_, i) => {caseIndex = i;lineIndex = 0;solution();
});