魔法装备管理系统（K0013）- 华为可信认证科目一方向 · 可信 / 贪心题解 | AlgoMooc

K0013. 魔法装备管理系统

中等

通过率 46% · 提交 162 · 通过 75

可信贪心系统设计哈希表模拟

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

魔法大陆上的每一种魔法装备都需要分配到一个特殊的魔法进程组进行管理，以保证它们能够正常运行。魔法装备类型编号为 `1`、`2` 和 `3`，对应的魔法进程组编号也为 `1`、`2` 和 `3`。每个魔法进程组包含若干，这些进程负责分配和管理魔法装备的内存。每个守护进程的编号从 `0` 开始，其内存容量为 `max_mem_size`。总共有 `proc_num` 个守护进程。您需要实现一个管理系统，支持以下三种操作： 1. 创建魔法装备为一个魔法装备分配内存并。优先选择最多的守护进程；如果空闲内存相同，选择编号较小的守护进程。如果没有守护进程能满足所需的内存，返回 `-1`。 2. 删除魔法装备释放指定魔法装备占用的内存，并从对应的守护进程解绑。如果该装备不存在，返回 `False`；否则返回 `True`。 3. 查询魔法装备返回某种类型的魔法装备信息，按以下规则排序： - 按消耗的内存大小 `mem_size` 降序； - 若内存相同，按绑定的守护进程编号 `proc_id` 升序； - 若仍相同，按魔法装备编号 `device_id` 升序。输入保证 `device_id` 唯一，不会重复创建相同编号的魔法装备。

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

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

输入描述

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

接下来有 Q 行：

如果操作是 初始化系统，输入格式为：
```
MagicDeviceMgtSystem
proc_num
max_mem_size
```
如果操作是 创建魔法装备，输入格式为：
```
create_device
device_id
device_type
mem_size
```
如果操作是 删除魔法装备，输入格式为：
```
delete_device
device_id
```
如果操作是 查询魔法装备，输入格式为：
```
query_device
device_type
```

输出描述

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

如果是初始化操作，输出 null；
如果是创建操作，输出绑定的守护进程编号；如果无法分配，输出 -1；
如果是删除操作，输出 True 或 False；
如果是查询操作，按格式输出查询到的装备信息，每行三个整数，分别表示 device_id、mem_size 和 proc_id。

示例

示例 1

输入示例

13
MagicDeviceMgtSystem
2
100
create_device
18
2
50
create_device
3
2
30
create_device
12
2
20
query_device
2
query_device
1
create_device
15
1
40
create_device
6
2
30
create_device
19
2
60
delete_device
18
create_device
26
2
70
query_device
1
query_device
2

输出示例

说明：

MagicDeviceMgtSystem(2, 100) create_device(18, 2, 50) create_device(3, 2, 30) create_device(12, 2, 20) query_device(2) query_device(1) create_device(15, 1, 40) create_device(6, 2, 30) create_device(19, 2, 60) delete_device(18) create_device(26, 2, 70) query_device(1) query_device(2)

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

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

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

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

from typing import List, Tuple

class MagicDeviceMgtSystem:
    def __init__(self, proc_num: int, max_mem_size: int):
        """
        Initialize the MagicDeviceMgtSystem with the given number of processes and maximum memory size per process.
        """
        pass

    def create_device(self, device_id: int, device_type: int, mem_size: int) -> int:
        """
        Create a device with given ID, type and required memory size.
        Returns the ID of the bound process or -1 if allocation fails.
        """
        pass

    def delete_device(self, device_id: int) -> bool:
        """
        Delete a device by its ID.
        Returns True if successful, False if the device does not exist.
        """
        pass

    def query_device(self, device_type: int) -> List[Tuple[int, int, int]]:
        """
        Query devices of a specific type.
        Returns a sorted list of tuples (device_id, mem_size, proc_id).
        """
        pass

# Driver code for input/output handling
system = None
Q = int(input())
for i in range(Q):
    cmd = input()
    if i == 0 and cmd == "MagicDeviceMgtSystem":
        proc_num = int(input())
        max_mem_size = int(input())
        system = MagicDeviceMgtSystem(proc_num, max_mem_size)
        print("null")
    elif i > 0 and cmd == 'create_device':
        device_id = int(input())
        device_type = int(input())
        mem_size = int(input())
        print(system.create_device(device_id, device_type, mem_size))
    elif i > 0 and cmd == "delete_device":
        device_id = int(input())
        print(system.delete_device(device_id))
    elif i > 0 and cmd == "query_device":
        device_type = int(input())
        ans = system.query_device(device_type)
        for u in ans:
            print(*u)
    else:
        assert False

from typing import List, Tuple

class MagicDeviceMgtSystem:
    def __init__(self, proc_num: int, max_mem_size: int):
        """
        Initialize the MagicDeviceMgtSystem with the given number of processes and maximum memory size per process.
        """
        pass

def create_device(self, device_id: int, device_type: int, mem_size: int) -> int:
        """
        Create a device with given ID, type and required memory size.
        Returns the ID of the bound process or -1 if allocation fails.
        """
        pass

def delete_device(self, device_id: int) -> bool:
        """
        Delete a device by its ID.
        Returns True if successful, False if the device does not exist.
        """
        pass

def query_device(self, device_type: int) -> List[Tuple[int, int, int]]:
        """
        Query devices of a specific type.
        Returns a sorted list of tuples (device_id, mem_size, proc_id).
        """
        pass

# Driver code for input/output handling
system = None
Q = int(input())
for i in range(Q):
    cmd = input()
    if i == 0 and cmd == "MagicDeviceMgtSystem":
        proc_num = int(input())
        max_mem_size = int(input())
        system = MagicDeviceMgtSystem(proc_num, max_mem_size)
        print("null")
    elif i > 0 and cmd == 'create_device':
        device_id = int(input())
        device_type = int(input())
        mem_size = int(input())
        print(system.create_device(device_id, device_type, mem_size))
    elif i > 0 and cmd == "delete_device":
        device_id = int(input())
        print(system.delete_device(device_id))
    elif i > 0 and cmd == "query_device":
        device_type = int(input())
        ans = system.query_device(device_type)
        for u in ans:
            print(*u)
    else:
        assert False

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

输入描述

输出描述

示例

我的提交