华为OD机试 - 贪心歌手 - 动态规划（Java 2024 D卷 200分）

本文主要是介绍华为OD机试 - 贪心歌手 - 动态规划（Java 2024 D卷 200分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

华为OD机试 2024C卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（D卷+C卷+A卷+B卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

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

按照合同，他必须在T天内赶到
歌手不能往回走
每两座城市之间需要的天数都可以提前获知。
歌手在每座城市都可以在路边卖唱赚钱。经过调研，歌手提前获知了每座城市卖唱的收入预期: 如果在一座城市第一天卖唱可以赚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

三、输出描述

一个数字。代表歌手最多可以赚多少钱。

1、输入

10 2
1 1 2
120 20
90 10

2、输出

540

3、说明

总共10天，路上经过2座城市。路上共花1+1+2=4天剩余6天最好的计划是
在第一座城市待3天，在第二座城市待3天在第一座城市赚的钱:120+100+80=300
在第二座城市赚的钱:90+80+70=240
一共300+240 = 540

四、解题思路

1、输入和初始化

输入总天数和城市数：读取总天数 t 和城市数 n。
计算必需的路程时间：遍历读入的每段路程所需的时间，累加以计算从城市A到城市B的全部必需路程时间 roadTime。
读取每个城市的卖唱收益信息：对于每个城市，读取初始收益 M 和每天的收益递减值 D，存储为二维数组 matrix。

2、主要算法逻辑

计算可用于赚钱的剩余天数：remain = t - roadTime。如果 remain 小于或等于零，输出0并结束程序。
使用优先队列优化收益管理：
- 初始化一个优先队列 priorityQueue，该队列用于存储在各个城市赚取的收益，队列的特性是始终将最小元素置于队顶，以此来保证总收益最大化。
- 遍历每个城市的收益数组 matrix。对于每个城市的初始收益 M 和递减值 D：
  - 从初始收益 M 开始，每一天递减 D，直到收益减至0或以下。
  - 对于每天的收益 m：
    - 收益替换逻辑：如果 priorityQueue 的大小达到了 remain（可用于赚钱的剩余天数），则检查当前收益 m 是否大于队列中的最小收益（队顶元素）：
    - 如果 m 大于队顶元素，弹出队顶元素并将 m 加入队列。
    - 如果 m 小于或等于队顶元素，停止当前城市的收益处理，因为后续的收益只会更低。
    - 如果队列大小未满，直接将 m 添加到队列中。

3、结果输出

使用 priorityQueue 中的所有值（即最终筛选出的最高收益天）的总和，作为最大可能赚到的总金额，打印此值作为最终结果。

这种方法通过优先队列控制和优化收益的存储与管理，保证了在限定的可赚钱天数内，每一天都能获得可能的最大收益。这样的策略对于动态调整哪一天的收益值应该被计算以最大化总收益是非常有效的。

五、Java算法源码

public class OdTest02 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int t = sc.nextInt();int n = sc.nextInt();// A到B必需的路程时间int roadTime = 0;for (int i = 0; i < n + 1; i++) {roadTime += sc.nextInt();}int[][] martrix = new int[n][2];for (int i = 0; i < n; i++) {martrix[i][0] = sc.nextInt();martrix[i][1] = sc.nextInt();}// 剩余可以用于赚钱的时间int remain = t - roadTime;// 如果没有剩余时间可以用，则直接返回0if (remain <= 0) {System.out.println(0);return;}// 优先队列，堆顶是赚的最少的钱PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();for (int[] arr : martrix) {int m = arr[0];int d = arr[1];int days = 0;while (m > 0) {if (priorityQueue.size() >= remain) {if (m > priorityQueue.peek()) {priorityQueue.poll();} else {break;}}priorityQueue.add(m);m -= d;days++;}}System.out.println(priorityQueue.stream().mapToInt(Integer::intValue).sum());}
}