題目描述

一個歌手準備從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();
});