最新华为OD机试真题-LYA的巡演(100分)

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

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

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

最新华为OD机试D卷目录，全、新、准，题目覆盖率达 95% 以上，支持题目在线评测

最新华为OD机试目录: https://www.nowcoder.com/discuss/636153620743897088?sourceSSR=users

📎在线评测链接

LYA的巡演(100分)

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

2️⃣ LYA的巡演

题目描述

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

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

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

输入格式

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

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

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

输出格式

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

样例输入

10 2
1 1 2
120 20
90 10

样例输出

540

样例解释

总共有 天时间,途中经过 座城市。从 城市到 城市共需要 天,剩余 天时间可以用来卖唱赚钱。最优方案是在第一座城市卖唱 天,在第二座城市卖唱 天。

在第一座城市可以赚 元,在第二座城市可以赚 元,总收入为 元。

数据范围

题解

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

具体步骤如下:

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

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

这样做的时间复杂度为 ,其中 为城市数量, 为某座城市第一天卖唱的收入, 为可以卖唱的总天数。排序的时间复杂度为 ,而遍历所有城市计算收入的时间复杂度为 。

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

参考代码

• Python

total_days, n = map(int, input().split())
travel_days = sum(map(int, input().split()))
sing_days = total_days - travel_days

incomes = []
for _ in range(n):
    first_day, dec = map(int, i