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

2024-06-05 10:20

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

在这里插入图片描述

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

专栏导读

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

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

一、题目描述

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

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

贪心的歌手最多可以赚多少钱?

二、输入描述

第一行两个数字 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、输入和初始化

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

2、主要算法逻辑

  1. 计算可用于赚钱的剩余天数:remain = t - roadTime。如果 remain 小于或等于零,输出0并结束程序。
  2. 使用优先队列优化收益管理:
    • 初始化一个优先队列 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());}
}

六、效果展示

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

在这里插入图片描述


🏆下一篇:华为OD机试 - 简易内存池 - 逻辑分析(Java 2024 C卷 200分)

🏆本文收录于,华为OD机试(JAVA)真题(D卷+C卷+A卷+B卷)

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

在这里插入图片描述

这篇关于华为OD机试 - 贪心歌手 - 动态规划(Java 2024 D卷 200分)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1032792

相关文章

Java学习手册之Filter和Listener使用方法

《Java学习手册之Filter和Listener使用方法》:本文主要介绍Java学习手册之Filter和Listener使用方法的相关资料,Filter是一种拦截器,可以在请求到达Servl... 目录一、Filter(过滤器)1. Filter 的工作原理2. Filter 的配置与使用二、Listen

Spring Boot中JSON数值溢出问题从报错到优雅解决办法

《SpringBoot中JSON数值溢出问题从报错到优雅解决办法》:本文主要介绍SpringBoot中JSON数值溢出问题从报错到优雅的解决办法,通过修改字段类型为Long、添加全局异常处理和... 目录一、问题背景:为什么我的接口突然报错了?二、为什么会发生这个错误?1. Java 数据类型的“容量”限制

Java对象转换的实现方式汇总

《Java对象转换的实现方式汇总》:本文主要介绍Java对象转换的多种实现方式,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录Java对象转换的多种实现方式1. 手动映射(Manual Mapping)2. Builder模式3. 工具类辅助映

SpringBoot请求参数接收控制指南分享

《SpringBoot请求参数接收控制指南分享》:本文主要介绍SpringBoot请求参数接收控制指南,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring Boot 请求参数接收控制指南1. 概述2. 有注解时参数接收方式对比3. 无注解时接收参数默认位置

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

SpringBoot项目中报错The field screenShot exceeds its maximum permitted size of 1048576 bytes.的问题及解决

《SpringBoot项目中报错ThefieldscreenShotexceedsitsmaximumpermittedsizeof1048576bytes.的问题及解决》这篇文章... 目录项目场景问题描述原因分析解决方案总结项目场景javascript提示:项目相关背景:项目场景:基于Spring

Spring Boot 整合 SSE的高级实践(Server-Sent Events)

《SpringBoot整合SSE的高级实践(Server-SentEvents)》SSE(Server-SentEvents)是一种基于HTTP协议的单向通信机制,允许服务器向浏览器持续发送实... 目录1、简述2、Spring Boot 中的SSE实现2.1 添加依赖2.2 实现后端接口2.3 配置超时时

Spring Boot读取配置文件的五种方式小结

《SpringBoot读取配置文件的五种方式小结》SpringBoot提供了灵活多样的方式来读取配置文件,这篇文章为大家介绍了5种常见的读取方式,文中的示例代码简洁易懂,大家可以根据自己的需要进... 目录1. 配置文件位置与加载顺序2. 读取配置文件的方式汇总方式一:使用 @Value 注解读取配置方式二

一文详解Java异常处理你都了解哪些知识

《一文详解Java异常处理你都了解哪些知识》:本文主要介绍Java异常处理的相关资料,包括异常的分类、捕获和处理异常的语法、常见的异常类型以及自定义异常的实现,文中通过代码介绍的非常详细,需要的朋... 目录前言一、什么是异常二、异常的分类2.1 受检异常2.2 非受检异常三、异常处理的语法3.1 try-

Java中的@SneakyThrows注解用法详解

《Java中的@SneakyThrows注解用法详解》:本文主要介绍Java中的@SneakyThrows注解用法的相关资料,Lombok的@SneakyThrows注解简化了Java方法中的异常... 目录前言一、@SneakyThrows 简介1.1 什么是 Lombok?二、@SneakyThrows