通关时间最短
🍀题目描述🌿解题思路🌸Python源码📧Summary
📆Date: 2023年1月3日 🎬Author: 小 y 同 学 📃Classify: 蓝桥杯每日一练 🔖Language: Python
🍀题目描述
题意 一个视频游戏有n个关卡，每个关卡需要看ai分钟视频和玩bi分钟才可以通关。必须将前面的关卡通过后，你才能接着玩后面的关卡，当你玩过一个关卡后，你可以跳过前面的视频直接玩这个关卡。现在有人想通关x次，通过的关卡可以任意选择，请问他至少要用多少时间。
输入格式 第一行包括两个正整数n,x，其中
1
≤
n
≤
2
×
1
0
5
,
1
≤
x
≤
1
0
9
1\le n\le 2\times10^5,\,1\le x\le 10^9
1≤n≤2×105,1≤x≤109 接下来n行每行两个整数ai,bi，其中
1
≤
A
i
,
B
i
≤
1
0
9
1\le A_i ,B_i\le 10^9
1≤Ai,Bi≤109
输出格式 一个正整数表示答案
样例输入1
3 4
3 4
2 3
4 2
样例输出1
18
样例输入2
10 1000000000
3 3
1 6
4 7
1 8
5 7
9 9
2 4
6 4
5 1
3 1
样例输出2
1000000076
🌿解题思路
题目梳理 初次读题并没有看懂意思，但是仔细梳理能知道题目的大概意思是：有一个包含n个关卡的看视频+玩游戏的游戏，通过关卡的条件是看ai分钟的视频+玩bi分钟的游戏，其他什么条件也没有，必须按照关卡的顺序来玩游戏；已通关的游戏可以再次玩但是第二次玩就不需要看ai分钟的视频直接消耗的是bi分钟的游戏时长。我们需要解决的就是在通关次数x(已经通关的关卡再次通关也计入)的前提下，所消耗的时间最少，输出最少的时间。数据输入 n,x直接常用套路输入语句n, x = map(int, input().split())然后小y是将ai和bi放在一个列表中然后添加到整个大列表中的。核心处理 首先我们通过观察可以发现：最优解一定是发生在通过了前j个关卡+第j个关卡玩x-j次这种情况，（不可能存在我玩到第j关，然后之前的某个关卡的bi较小，所以剩余的次数我一直玩那个关卡；因为如果是这个情况的话，何不直接以那个bi较小的关卡作为最终重复通关的关卡？）；如果这个可以理解的话，我们可以通过计算通过的最后一关也就是第j关从1到n的所有类似最优解的结构的结果，从这些结果中找出最小值即可。本程序中需要注意j是从第0个关卡开始计算的。
🌸Python源码
# _*_coding:utf-8_*_
# created by cy on 2023/1/3
def solve():
# 数据输入
result = [] # 计算结果存储
n, x = map(int, input().split())
ab_li = []
# ai,bi的输入
for k in range(n):
tem = list(map(int, input().split()))
ab_li.append(tem)
Num = 0 # Num存储第一次玩关卡的分钟总和
for j in range(n):
Num += sum(ab_li[j])
# sun_存储Num加上最后一个关卡重复玩的时间需要注意j从0开始计数
sum_ = Num + (x - 1 - j) * ab_li[j][1]
result.append(sum_)
print(min(result))
if __name__ == "__main__":
solve()
📧Summary
小y的今日一练到此画上了句号,对于这题,小y的思路也仅仅局限于此,欢迎友友们多给建议🌼🌼🌼 有兴趣一起学习编程的小伙伴可以私聊小y一起学习,小y在Python,c/c++和matlab语言上均有一定的基础😜😜😜
欢迎您的点赞👍+收藏🎁+关注❤ 😁😁😁