20260923-世界杯徽章换购（N0079）- 算法机考高频题型 · 华为OD / 100分题解 | AlgoMooc

N0079. 20260923-世界杯徽章换购

中等

通过率 78% · 提交 9 · 通过 7

100分华为OD贪心

本题改编自算法机考高频题型 · 考点：100分 / 华为OD · 难度：中等

球迷排成一队换购世界杯徽章。换购规则如下：

从队头开始，依次为每人换购 1 枚徽章，每次换购耗时 1 个单位时间；若该球迷仍有未换完的徽章，则重新排到队尾继续等待；若该球迷所有徽章已换完，则直接离队，不再参与后续排队。

给定每人需要换购的徽章数量数组 medals 和目标球迷下标 k，求当数组下标第 k 号球迷换完所有徽章时，总耗时为多少？

这类题属于算法机考高频题型中「100分 / 华为OD」方向的高频题型，通常考察对「100分 / 华为OD」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。

输入描述

medals：长度为 n 的正整数数组，medals[i] 表示数组下标第 i 号球迷需要换购的徽章数； k：目标球迷所在的数组下标，输入保证 0 <= k < n；

输出描述

输出一个整数，表示当数组下标第 k 号球迷换完所有徽章时的总耗时。

示例

示例 1

输入示例

3
2 3 2
2

输出示例

说明：

初始队伍：[0号(2), 1号(3), 2号(2)]，其中 2 号是目标球迷。

第 1 轮遍历： 0 号换 1 枚，剩余 1，排到队尾，耗时 + 1（累计 1） 1 号换 1 枚，剩余 2，排到队尾，耗时 + 1（累计 2） 2 号换 1 枚，剩余 1，排到队尾，耗时 + 1（累计 3）队伍变为：[0号(1), 1号(2), 2号(1)]。

第 2 轮遍历： 0 号换 1 枚，剩余 0，离队，耗时 + 1（累计 4） 1 号换 1 枚，剩余 1，排到队尾，耗时 + 1（累计 5） 2 号换 1 枚，剩余 0，换完离队，耗时 + 1（累计 6）

2 号球迷已换完所有徽章，总耗时 = 6。

示例 2

输入示例

3
1 5 3
1

输出示例

说明：

数组下标 1 号球迷需要换购 5 个徽章，第 1 轮结束 0 号离队（累计 3）；第 3 轮结束 2 号离队（累计 3 + 2 + 2 = 7）；第 5 轮结束 1 号全部换购（累计 3 + 2 + 2 + 1 + 1 = 9）。

时间限制 1000 ms · 内存限制 256 MB

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

问小欧 · 图解算法年卡¥99 开通 →

未登录也能直接「运行」调试;「提交」判题需微信登录,你写的代码会自动保留、登录后回到本题继续。

字号13Ctrl+/ 注释 · Ctrl+↵ 提交

from typing import List

class Solution:
    def timeRequiredToBuy(self, medals: List[int], k: int) -> int:
        return 0

if __name__ == "__main__":
    import sys
    input = sys.stdin.readline
    
    n = int(input().strip())
    medals = list(map(int, input().strip().split()))
    k = int(input().strip())
    
    sol = Solution()
    print(sol.timeRequiredToBuy(medals, k))

写完代码点「提交」，将对全部测试用例判题。

输入描述

输出描述

示例

我的提交