魔法卷轴封印系统（K0027）- 华为可信认证科目一方向 · 可信 / 系统设计题解 | AlgoMooc

K0027. 魔法卷轴封印系统

中等

通过率 63% · 提交 102 · 通过 64

可信系统设计队列

本题改编自华为可信认证科目一方向 · 考点：可信 / 系统设计 · 难度：中等

在亚兰泽斯魔法大陆，魔导师们管理着无数蕴含强大魔力的。这些卷轴必须按照严格的封印规则存放至中，否则魔法可能会失控，引发灾难。为此，魔法工程师们设计了一套，用于高效管理魔法卷轴。系统按照以下规则运行： 1. 初始化封印系统：设置封印规则，包括 `timeWindow`、最大封印卷轴数 `maxFiles`、封印卷轴的魔法总量上限 `fileSize`。 2. 创建魔法卷轴：每个卷轴按照时间顺序生成（严格递增），并带有唯一的编号 `fileId` 和魔法能量值 `fileSize`。 3. 执行封印：选择满足条件的卷轴，将其打包进魔法典籍中。你的任务是实现这个魔法封印系统，使卷轴能够按照规则正确封印。

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

提示：带虚线的词点一下有通俗解释。

输入描述

第一行包含一个整数 Q，表示操作的总数。

接下来的 Q 行，每行描述一个操作，操作分为以下几种：

初始化封印系统：
- 命令：ZipSystem
- 参数：
  - timeWindow：时间窗口 T，表示卷轴的时间戳与队列中第一个卷轴的时间戳之差不能超过 T。
  - maxFiles：最大封印卷轴数 M，表示每次封印操作最多可以封印 M 个卷轴。
  - maxSize：魔法总量上限 S，表示每次封印操作的卷轴魔法能量值之和不能超过 S。
插入卷轴：
- 命令：insertFile
- 参数：
  - timestamp：卷轴的时间戳。
  - fileId：卷轴的唯一编号。
  - fileSize：卷轴的魔法能量值。
执行封印：
- 命令：zip
- 参数：无

输出描述

对于每个操作，输出相应的结果：

初始化封印系统：
- 输出："null"，表示初始化完成。
插入卷轴：
- 输出：当前队列中的卷轴数量。
执行封印：
- 输出：封印的卷轴编号列表，按升序排列，编号之间用空格分隔。如果没有满足条件的卷轴，输出空行。

示例

示例 1

输入示例

12
ZipSystem
10
3
15
insertFile
1
101
5
insertFile
2
102
4
insertFile
3
103
6
insertFile
5
104
3
insertFile
15
105
7
zip
insertFile
17
107
4
insertFile
20
94
3
zip
insertFile
20
85
1
zip

输出示例

null
1
2
3
4
5
101 102 103
3
4
104 105
3
85 94 107

说明：

在这个示例中，魔法封印系统按照以下步骤运行：

初始化封印系统：设置时间窗口 T=10，最大封印卷轴数 M=3，魔法总量上限 S=15。系统初始化完成后输出 "null"。
插入卷轴：
- 插入卷轴 (1, 101, 5)，队列中有 1 个卷轴，输出 1。
- 插入卷轴 (2, 102, 4)，队列中有 2 个卷轴，输出 2。
- 插入卷轴 (3, 103, 6)，队列中有 3 个卷轴，输出 3。
- 插入卷轴 (5, 104, 3)，队列中有 4 个卷轴，输出 4。
- 插入卷轴 (15, 105, 7)，队列中有 5 个卷轴，输出 5。
第一次执行封印：
- 选择满足条件的卷轴 101、102、103，它们的魔法能量值之和为 5 + 4 + 6 = 15，未超过 S=15，且时间戳差不超过 T=10。
- 封印后输出 101 102 103，队列中剩余卷轴 (5, 104, 3) 和 (15, 105, 7)。
继续插入卷轴：
- 插入卷轴 (17, 107, 4)，队列中有 3 个卷轴，输出 3。
- 插入卷轴 (20, 94, 3)，队列中有 4 个卷轴，输出 4。
第二次执行封印：
- 选择满足条件的卷轴 104 和 105，它们的魔法能量值之和为 3 + 7 = 10，未超过 S=15，且时间戳差不超过 T=10。
- 封印后输出 104 105，队列中剩余卷轴 (17, 107, 4) 和 (20, 94, 3)。
继续插入卷轴：
- 插入卷轴 (20, 85, 1)，队列中有 3 个卷轴，输出 3。
第三次执行封印：
- 选择满足条件的卷轴 85、94、107，它们的魔法能量值之和为 1 + 3 + 4 = 8，未超过 S=15，且时间戳差不超过 T=10。
- 封印后输出 85 94 107，队列为空。

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

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

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

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

from typing import List

class ZipSystem:
    def __init__(self, timeWindow: int, maxFiles: int, maxSize: int):
        # 构造函数，初始化封印系统参数
        pass

    def insertFile(self, timestamp: int, fileId: int, fileSize: int) -> int:
        # 插入一个新的魔法卷轴，返回当前队列大小
        return 0

    def zip(self) -> List[int]:
        # 执行一次封印操作，返回被封印的卷轴编号列表
        return []

system = None
Q = int(input())
for i in range(Q):
    cmd = input()
    if i == 0 and cmd == "ZipSystem":
        timeWindow = int(input())
        maxFiles = int(input())
        maxSize = int(input())
        system = ZipSystem(timeWindow, maxFiles, maxSize)
        print("null")
    elif i > 0 and cmd == 'insertFile':
        timestamp = int(input())
        fileId = int(input())
        fileSize = int(input())
        print(system.insertFile(timestamp, fileId, fileSize))
    elif i > 0 and cmd == "zip":
        ans = system.zip()
        print(" ".join(map(str, ans)))
    else:
        assert False

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

输入描述

输出描述

示例

我的提交