題目解析

題目描述：
歌手準備從 A 城去 B 城參加演出

1. 按照合同，他必須在 T 天內趕到。
2. 歌手途徑 N 座城市。歌手不能往回走。
3. 每兩座城市之間需要的天數都可以提前獲知。
4. 歌手在每座城市都可以在路邊賣唱賺錢。經過調研，歌手提前獲知了每座城市賣唱的收入預期。如果在一座城市第一天賣唱可以賺 M，后續每天的收入會減少 D (第二天賺的錢是 M-D，第三天是 M-2D…)。如果收入減到 0 就不會再少了。
5. 歌手到達后的第二天才能開始賣唱。如果今天賣過唱，第二天才能出發（即按整天算）。

輸出：
輸出歌手在旅途中最多能掙多少錢。

輸入描述：
第一行兩個數字 T 和 N，中間用空格隔開。

T 代表總天數，0 < T < 1000N 代表路上經過 N 座城市，0 < N < 100

第二行 N+1 個數字，中間用空格隔開。代表每兩座城市之間耗費的時間。其總和 ≤ T。

接下來 N 行，每行兩個數字 M 和 D，中間用空格隔開。代表每個城市的輸入預期。

0 < M < 10000 < 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

題解

題目已經告訴了總天數T、走完整個旅途在路上所需的天數roadCost，因此可以知道 在途中唱歌賣藝掙錢的天數remain。
也就是說，題目可以轉換為，在remain天內，最多可以掙多少錢。
旅途中，每天可以掙錢數目為：

m1, m1-d1, .... (m1- remain*d1) 
...
mn, mn-dn, .... (mn- remain*dn) 【每個元素都需要>0】

即，是在上面的范圍內選擇。因此有兩種思路：（都是貪心思路，每次都選取當前最優解）

1. 將上面的選項數值全部先計算出來，然后選取其中前remain個最大的，然后算出總和就可以得到結果；
2. 使用（最小堆）優先隊列，將這些結果依次裝入隊列中， 如果當前待裝入的值：(即，每次裝入的值要盡可能的大)
   • 大于隊列中的最小值，則將該最小值拋棄，接納該待裝入的值；
   • 小于隊列中的最小值，則什么都不做。

到最后，隊列中剩余的remain個元素，就是選項范圍內的前remian個最大的值，算出總和就是結果。

代碼：

public class Greedy_Singer {static int t; // 總天數static int n; // 城市數量static int roadCost; // 旅途中花費在路上的時間static int[][] mds; // 每個城市的 預期收入 與 遞減值public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 讀取 總天數t 和 城市數量nt = sc.nextInt();n = sc.nextInt();// 讀取 城市間的旅行時間，并計算花費在路上的時間 roadCostroadCost = 0;for (int i = 0; i < n+1; i++) {roadCost += sc.nextInt();}// 讀取每個城市的收入預期M 和 遞減值Dmds = new int[n][2];for (int i = 0; i < n; i++) {mds[i][0] = sc.nextInt();mds[i][1] = sc.nextInt();}// 輸出最大收益System.out.println(getResult());}public static int getResult() {// 計算用于賣唱的時間(天)int remain = t - roadCost;// 如果剩余天數 ≤0，則直接返回0if (remain <= 0) {return 0;}// 使用優先隊列（最小堆）來存儲收益PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> a - b);// 遍歷每個城市for (int[] md : mds) {int m = md[0];int d = md[1];// 計算每天的收益，并將其添加到優先隊列中while (m > 0) {// (貪心選取，當隊列滿了（隊列大小 = 剩余天數）之后，需要每次選取當前可知的較大者)// 如果 優先隊列大小 已經 達到剩余天數了，則需要比較當前收益 與 隊列中最小值if (pq.size() >= remain) {if (m > pq.peek()) {pq.poll(); // 彈出最小值} else {break; // 如果當前收益小于隊列中的最小值，則不添加 當前的這個值}}pq.add(m); // 將當前收益添加到隊列中m -= d;}}// 計算出優先隊列中所有收益的總和return pq.stream().reduce(Integer::sum).orElse(0);}
}