代码收藏家 华为OD机试E卷Java贪心歌手专项解析
题目描述
一个歌手准备从A城去B城参加演出。
-
按照合同，他必须在 T 天内赶到
-
歌手途经 N 座城市
-
歌手不能往回走
-
每两座城市之间需要的天数都可以提前获知。
-
歌手在每座城市都可以在路边卖唱赚钱。
经过调研，歌手提前获知了每座城市卖唱的收入预期： 如果在一座城市第一天卖唱可以赚M，后续每天的收入会减少D（第二天赚的钱是 M – D，第三天是 M – 2D …）。如果收入减少到 0 就不会再少了。
-
歌手到达后的第二天才能开始卖唱。如果今天卖过唱，第二天才能出发。
贪心的歌手最多可以赚多少钱？
输入描述
第一行两个数字 T 和 N，中间用空格隔开。
第二行 N+1 个数字，中间用空格隔开。代表每两座城市之间耗费的时间。
接下来 N 行，每行两个数字 M 和 D，中间用空格隔开。代表每个城市的输入预期。
输出描述
一个数字。代表歌手最多可以赚多少钱。以回车结束。
用例
输入
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。
解题思路
贪心算法
贪心算法在此问题中的应用
-
最大化每天收益：对于每个城市，根据其收入预期M和收入递减值D，可以计算出如果在该城市卖唱，每一天的收益是多少。随着时间的推移，这个城市的日收益会递减。在这个过程中，算法每天都会计算并尝试选择当天的最大可能收益。
-
选择最佳卖唱天数：由于总天数T是有限的，所以需要在所有可选的卖唱天数中挑选出最有利的组合。这里的贪心选择是通过优先队列（最小堆）来实现的。优先队列中存储的是当前选择的卖唱天数的收益。如果遇到一个新的天数其收益比队列中最小的收益要高，那么就替换掉这个最小收益的天数。这样，我们总是保持了收益最大化的天数组合。
具体 步骤
-
初始化一个优先队列，用于记录每天的收益。优先队列的特性是，队列中的元素总是按照一定的顺序排列，这里是按照收益的大小排列。
-
遍历每个城市，对于每个城市
作者：算法大师
