首页 > 试题广场 >

小红闯关

[编程题]小红闯关
  • 热度指数：4420 时间限制：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

说明

\,\,\,\,\,\,\,\,\,\,通过第一关后，后面的关卡都可以使用跳关道具。跳关也算一次成功的闯关。
算法知识视频讲解
添加回答
Python3
牛客156913013号头像 牛客156913013号
桶思想+并查集

为啥想桶? 对于每一关, 可能拥有的最大票数是固定的, 为(idx//k), 从整数除法提示我们可以选择把它们看成一个个桶.
但这些桶可能会合并. 比如说, 我使用了第i个桶的一张票, 那第i个桶还能用票吗? 答案是可以的, 它还能用第i-1个桶的票. 所以, 最好用完第i个桶的票后, 就把第i个桶和第i-1个桶合并.

合并两个集合的最常用方法就是并查集. 合并操作用来合并桶, 查询操作用来查询指定桶现在有哪个桶的票. 
ans = sum(arr)
m = (n - 1) // k

if m == 0:
    print(ans)
else:
    sort_arr = sorted(range(n), key=lambda i: -arr[i])
    
    buckets = list(range(m+2))

    def find(x):
        if buckets[x] == x:
            return x
        buckets[x] = find(buckets[x])
        return buckets[x]

    def union(a, b):
        buckets[a] = find(buckets[b])

    use_cnt = 0
    for idx in sort_arr:
        bucket = idx // k

        if bucket < 1:
            continue
        tickt = find(bucket)
        if tickt >= 1:
            use_cnt += 1
            ans -= arr[idx]
            union(tickt, tickt-1)
            if use_cnt == m:
                break
    print(ans)


发表于 2025-08-30 21:16:13 回复(0)
提交观点

问题信息

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

热门推荐

相关试题

小红闯关

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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