首页 > 试题广场 >

小红闯关

[编程题]小红闯关
  • 热度指数：4472 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\,\,\,\,\,\,\,\,\,\,小红在玩一个游戏，这个游戏有 n 个关卡，通过第 i 个关卡需要消耗 a_i 个单位时间，小红必须按从前往后的顺序通过每一个关卡。
\,\,\,\,\,\,\,\,\,\,每通过 k 个关卡，小红会获得一个跳关道具，跳关道具可以在任意一个关卡使用，使用跳关道具后可以不消耗时间直接通过关卡。
\,\,\,\,\,\,\,\,\,\,小红想知道她通过这 n 个关卡，最少需要多少时间。

输入描述:
\,\,\,\,\,\,\,\,\,\,第一行输入两个整数 n, k\left(1 \leq n, k \leq 10^5\right) 代表关卡数量和获得跳关道具的条件。
\,\,\,\,\,\,\,\,\,\,第二行输入 n 个整数 a_1, a_2, \dots, a_n\left(1 \leq a_i \leq 10^5\right) 代表通过每个关卡需要消耗的时间。


输出描述:
\,\,\,\,\,\,\,\,\,\,在一行上输出一个整数，表示小红通过这 n 个关卡所需的最少时间。
示例1

输入

3 2
1 3 2

输出

4

说明

\,\,\,\,\,\,\,\,\,\,小红通过第二个关卡后获得跳关道具，此时消耗 1+3 单位时间；在第三个关卡使用跳关道具，不再消耗时间。
示例2

输入

6 2
1 1 4 5 1 4

输出

7

说明

\,\,\,\,\,\,\,\,\,\,小红通过第二个关卡后获得第一个跳关道具；
\,\,\,\,\,\,\,\,\,\,在第四个关卡使用第一个跳关道具后得到第二个跳关道具；
\,\,\,\,\,\,\,\,\,\,在第六个关卡使用第二个跳关道具。
示例3

输入

5 1
2 4 5 1 3

输出

2

说明

\,\,\,\,\,\,\,\,\,\,通过第一关后，后面的关卡都可以使用跳关道具。跳关也算一次成功的闯关。
算法知识视频讲解
添加回答
Python
牛客90374346号头像 牛客90374346号 
import sys

for line in sys.stdin:
    a = line.split()
    n, k = int(a[0]), int(a[1])
    num = list(map(int, input().split()))
    jump = n // k  # 有多少次跳的机会
    chance = [1] * (jump + 1)

    # 为每个元素添加索引信息，形成 (index, value) 元组
    num_with_index = [(i, v) for i, v in enumerate(num)]
    # 按照值从大到小排序
    maxnum = sorted(num_with_index, key=lambda x: x[1], reverse=True)

    jian = 0
    for i, x in maxnum:
        j = i // k  # 看在第几次能 jump
        for p in range(j, 0, -1):
            if chance[p] == 1:
                chance[p] = 0
                jump -= 1
                jian += x
                break
        if jump == 0:
            break      print(sum([x[1] for x in maxnum]) - jian)
有点超时了，15/20个用例通过，比一楼的答案通过更多
发表于 2025-03-23 17:21:32 回复(0)
提交观点

问题信息

贪心 堆 阿里云
难度：
1条回答 1521浏览

热门推荐

相关试题

小红闯关

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号