【2024最新华为OD-C/D卷试题汇总】[支持在线评测] LYA的巡演(100分)

本文主要是介绍【2024最新华为OD-C/D卷试题汇总】[支持在线评测] LYA的巡演(100分) - 三语言AC题解(Python/Java/Cpp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解

💻 ACM银牌🥈| 多次AK大厂笔试｜编程一对一辅导

👏 感谢大家的订阅➕ 和喜欢💗

📎在线评测链接

https://app5938.acapp.acwing.com.cn/contest/2/problem/OD1073
🌍 评测功能需要 ⇒ 订阅专栏 ⇐ 后私信联系清隆解锁～

🍓OJ题目截图

在这里插入图片描述

文章目录

- 📎在线评测链接
- 🍓OJ题目截图
- LYA的巡演
- - 题目描述
  - 输入格式
  - 输出格式
  - 样例输入
  - 样例输出
  - 样例解释
  - 数据范围
  - 题解
  - 题解
  - 参考代码

LYA的巡演

题目描述

LYA是一位歌手,她计划从 $A$ 城市出发,在 $T$ 天内到达 $B$ 城市参加演出。途中,LYA会经过 $N$ 座城市,每两座城市之间需要耗费一定的时间。LYA不能往回走,但可以在每座城市逗留卖唱赚钱。

LYA提前了解到,在一座城市卖唱第一天可以赚 $M$ 元,之后每天的收入会减少 $D$ 元,直到减为 $0$ 为止。LYA只有在到达一座城市的第二天才能开始卖唱,如果当天卖过唱,就要等到第二天才能出发去下一座城市。

作为一位贪心的歌手,LYA希望在规定时间内赚到最多的钱。你能帮她算算最多能赚多少钱吗?

输入格式

第一行包含两个正整数 $T$ 和 $N$ ,分别表示总天数和途中经过的城市数量,满足 $0 < T < 1000$ , $0 < N < 100$ 。

第二行包含 $N + 1$ 个正整数,表示每两座城市之间需要耗费的时间,它们的总和不超过 $T$ 。

接下来 $N$ 行,每行包含两个正整数 $M$ 和 $D$ ,分别表示在对应城市卖唱第一天的收入和之后每天收入减少的值,满足 $0 < M < 1000$ , $0 < D < 100$ 。

输出格式

输出一个整数,表示LYA最多能赚到的钱数。

样例输入

样例输出

样例解释

总共有 $10$ 天时间,途中经过 $2$ 座城市。从 $A$ 城市到 $B$ 城市共需要 $1 + 1 + 2 = 4$ 天,剩余 $6$ 天时间可以用来卖唱赚钱。最优方案是在第一座城市卖唱 $3$ 天,在第二座城市卖唱 $3$ 天。

在第一座城市可以赚 $120 + 100 + 80 = 300$ 元,在第二座城市可以赚 $90 + 80 + 70 = 240$ 元,总收入为 $300 + 240 = 540$ 元。

数据范围

$0 < T < 1000$
$0 < N < 100$
$0 < M < 1000$
$0 < D < 100$

题解

抱歉,我的题解写得不够准确。根据之前给出的Python代码,这道题确实可以用贪心策略来解决。让我重新写一份题解:

题解

这道题可以使用贪心策略来解决。我们可以先计算出歌手总共有多少天可以用来卖唱赚钱,然后将每座城市每天的收入按从大到小排序,取前 $k$ 大的值相加即可,其中 $k$ 为可以卖唱的总天数。

具体步骤如下:

计算歌手总共可以卖唱的天数 $k$ ,即总天数 $T$ 减去城市间移动需要的天数之和。
遍历每座城市,计算出在该城市卖唱每天的收入,直到收入减为 $0$ ,将所有的收入值加入数组 $in co m es$ 。
将数组 $in co m es$ 按照从大到小的顺序排序。
取排序后的数组 $in co m es$ 的前 $k$ 个元素求和,即为歌手能赚到的最大收入。

为什么这样做是正确的呢?因为我们要在有限的天数内尽可能多地赚钱,所以应该优先选择每天收入最高的城市去卖唱。将所有城市的每天收入排序后,前 $k$ 大的收入对应的就是歌手应该选择去卖唱的日子。

这样做的时间复杂度为 $\times \max(M) + k \log k)$ ,其中 $N$ 为城市数量, $M$ 为某座城市第一天卖唱的收入, $k$ 为可以卖唱的总天数。排序的时间复杂度为 $\log k)$ ,而遍历所有城市计算收入的时间复杂度为 $\times \max(M))$ 。

这种贪心策略是最优的,因为它总是选择了当前收入最高的日子去卖唱,不会遗漏任何可能获得更多收入的机会。

参考代码

Python

total_days, n = map(int, input().split())
travel_days = sum(map(int, input().split()))
sing_days = total_days - travel_daysincomes = []
for _ in range(n):first_day, dec = map(int, input().split())cur_income = first_daywhile cur_income > 0:incomes.append(cur_income)cur_income -= decincomes.sort(reverse=True)
print(sum(incomes[:sing_days]))

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int totalDays = sc.nextInt();int n = sc.nextInt();int travelDays = 0;for (int i = 0; i < n + 1; i++) {travelDays += sc.nextInt();}int singDays = totalDays - travelDays;ArrayList<Integer> incomes = new ArrayList<>();for (int i = 0; i < n; i++) {int firstDay = sc.nextInt();int dec = sc.nextInt();int curIncome = firstDay;while (curIncome > 0) {incomes.add(curIncome);curIncome -= dec;}}Collections.sort(incomes, Collections.reverseOrder());int maxIncome = 0;for (int i = 0; i < singDays; i++) {maxIncome += incomes.get(i);}System.out.println(maxIncome);}
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main() {int totalDays, n;cin >> totalDays >> n;int travelDays = 0;for (int i = 0; i < n + 1; i++) {int d;cin >> d;travelDays += d;}int singDays = totalDays - travelDays;vector<int> incomes;for (int i = 0; i < n; i++) {int firstDay, dec;cin >> firstDay >> dec;int curIncome = firstDay;while (curIncome > 0) {incomes.push_back(curIncome);curIncome -= dec;}}sort(incomes.begin(), incomes.end(), greater<int>());int maxIncome = 0;for (int i = 0; i < singDays; i++) {maxIncome += incomes[i];}cout << maxIncome << endl;return 0;
}