当前位置：首页 > news >正文

华为OD机试 - 贪心歌手 - 动态规划（Python/JS/C/C++ 2024 D卷 200分）

news 2024/10/21 10:40:04

在这里插入图片描述

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

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。

一、题目描述

一个歌手准备从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 中的所有值（即最终筛选出的最高收益天）的总和，作为最大可能赚到的总金额，打印此值作为最终结果。

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

六、Python算法源码

def main():import sys# 读取所有输入并拆分为列表input = sys.stdin.read().split()idx = 0T = int(input[idx]); idx += 1  # 总天数TN = int(input[idx]); idx += 1  # 城市数量N# 读取A到B的路程时间roadTimes = []totalRoadTime = 0for _ in range(N + 1):roadTime = int(input[idx]); idx += 1roadTimes.append(roadTime)totalRoadTime += roadTime  # 累加总路程时间# 读取每个城市的M和Dcities = []for _ in range(N):M = int(input[idx]); idx += 1  # 第一天的收入MD = int(input[idx]); idx += 1  # 收入递减值Dcities.append((M, D))# 计算剩余可用于卖唱的天数sellDays = T - totalRoadTimeif sellDays <= 0:print(0)  # 如果没有剩余时间，收益为0return# 初始化动态规划数组，dp[j]表示使用j天卖唱的最大收益dp = [0] * (sellDays + 1)# 遍历每个城市for i in range(N):M, D = cities[i]# 计算当前城市在不同卖唱天数下的最大收益earn = [0] * (sellDays + 1)for d in range(1, sellDays + 1):if d == 1:earn[d] = M  # 第一天的收入else:earn[d] = max(earn[d - 1] + max(M - (d - 1) * D, 0), earn[d - 1])# 更新动态规划数组for d in range(sellDays, 0, -1):for k in range(1, d + 1):dp[d] = max(dp[d], dp[d - k] + earn[k])# 计算并输出最大收益maxEarn = max(dp)print(maxEarn)if __name__ == "__main__":main()

七、JavaScript算法源码

function main() {const fs = require('fs'); // 引入文件系统模块const input = fs.readFileSync('/dev/stdin', 'utf8').trim().split(/\s+/); // 读取并拆分输入let idx = 0;const T = parseInt(input[idx++]); // 总天数Tconst N = parseInt(input[idx++]); // 城市数量N// 读取A到B的路程时间const roadTimes = [];let totalRoadTime = 0;for (let i = 0; i < N + 1; i++) {const roadTime = parseInt(input[idx++]);roadTimes.push(roadTime);totalRoadTime += roadTime; // 累加总路程时间}// 读取每个城市的M和Dconst cities = [];for (let i = 0; i < N; i++) {const M = parseInt(input[idx++]); // 第一天的收入Mconst D = parseInt(input[idx++]); // 收入递减值Dcities.push([M, D]);}// 计算剩余可用于卖唱的天数const sellDays = T - totalRoadTime;if (sellDays <= 0) {console.log(0); // 如果没有剩余时间，收益为0return;}// 初始化动态规划数组，dp[j]表示使用j天卖唱的最大收益const dp = Array(sellDays + 1).fill(0);// 遍历每个城市for (let i = 0; i < N; i++) {const [M, D] = cities[i];// 计算当前城市在不同卖唱天数下的最大收益const earn = Array(sellDays + 1).fill(0);for (let d = 1; d <= sellDays; d++) {if (d === 1) {earn[d] = M; // 第一天的收入} else {earn[d] = Math.max(earn[d - 1] + Math.max(M - (d - 1) * D, 0), earn[d - 1]);}}// 更新动态规划数组for (let d = sellDays; d >= 1; d--) {for (let k = 1; k <= d; k++) {dp[d] = Math.max(dp[d], dp[d - k] + earn[k]);}}}// 计算并输出最大收益const maxEarn = Math.max(...dp);console.log(maxEarn);
}main();

八、C算法源码

#include <stdio.h>
#include <stdlib.h>// 定义一个函数来返回两个整数中的较大值
int max(int a, int b){return (a > b) ? a : b;
}int main(){int T, N;scanf("%d %d", &T, &N); // 读取总天数T和城市数量N// 读取A到B的路程时间int roadTimes[N + 1];int totalRoadTime = 0;for(int i = 0; i < N + 1; i++){scanf("%d", &roadTimes[i]);totalRoadTime += roadTimes[i]; // 累加总路程时间}// 读取每个城市的M和Dint cities[N][2];for(int i = 0; i < N; i++){scanf("%d %d", &cities[i][0], &cities[i][1]); // cities[i][0]=M, cities[i][1]=D}// 计算剩余可用于卖唱的天数int sellDays = T - totalRoadTime;if(sellDays <= 0){printf("0\n"); // 如果没有剩余时间，收益为0return 0;}// 初始化动态规划数组，dp[j]表示使用j天卖唱的最大收益int *dp = (int*)calloc(sellDays + 1, sizeof(int));// 遍历每个城市for(int i = 0; i < N; i++){int M = cities[i][0];int D = cities[i][1];// 计算当前城市在不同卖唱天数下的最大收益int earn[sellDays + 1];earn[0] = 0;for(int d = 1; d <= sellDays; d++){if(d == 1){earn[d] = M; // 第一天的收入}else{earn[d] = max(earn[d - 1] + ((M - (d - 1) * D) > 0 ? (M - (d - 1) * D) : 0), earn[d - 1]);}}// 更新动态规划数组for(int d = sellDays; d >= 1; d--){for(int k = 1; k <= d; k++){if(dp[d] < dp[d - k] + ((M - (k - 1) * D) > 0 ? (M - (k - 1) * D) : 0)){dp[d] = dp[d - k] + ((M - (k - 1) * D) > 0 ? (M - (k - 1) * D) : 0);}}}}// 计算最大收益int maxEarn = 0;for(int i = 0; i <= sellDays; i++){if(dp[i] > maxEarn){maxEarn = dp[i];}}printf("%d\n", maxEarn); // 输出最大收益free(dp); // 释放动态分配的内存return 0;
}

九、C++算法源码

#include <bits/stdc++.h>
using namespace std;int main(){int T, N;cin >> T >> N; // 读取总天数T和城市数量N// 读取A到B的路程时间vector<int> roadTimes(N + 1);int totalRoadTime = 0;for(int i = 0; i < N + 1; i++){cin >> roadTimes[i];totalRoadTime += roadTimes[i]; // 累加总路程时间}// 读取每个城市的M和Dvector<pair<int, int>> cities(N);for(int i = 0; i < N; i++){cin >> cities[i].first >> cities[i].second; // cities[i].first=M, cities[i].second=D}// 计算剩余可用于卖唱的天数int sellDays = T - totalRoadTime;if(sellDays <= 0){cout << "0" << endl; // 如果没有剩余时间，收益为0return 0;}// 初始化动态规划数组，dp[j]表示使用j天卖唱的最大收益vector<int> dp(sellDays + 1, 0);// 遍历每个城市for(int i = 0; i < N; i++){int M = cities[i].first;int D = cities[i].second;// 计算当前城市在不同卖唱天数下的最大收益vector<int> earn(sellDays + 1, 0);for(int d = 1; d <= sellDays; d++){if(d == 1){earn[d] = M; // 第一天的收入}else{earn[d] = max(earn[d - 1] + max(M - (d - 1) * D, 0), earn[d - 1]);}}// 更新动态规划数组for(int d = sellDays; d >= 1; d--){for(int k = 1; k <= d; k++){dp[d] = max(dp[d], dp[d - k] + earn[k]);}}}// 计算并输出最大收益int maxEarn = *max_element(dp.begin(), dp.end());cout << maxEarn << endl;return 0;
}