#P1230. 2023.04.26-实习-第二题-分配资源ID

2023.04.26-实习-第二题-分配资源ID

注意:

100ms,基本就意味着除cpp以外,其他语言不太能通过了。

--------------------4-27更新----------------

根据群友消息,由于本场题目确实太难,相较通过率太低,所以华子HR决定这次没过的可以重考,参加下次的5.6的笔试!

题目内容

你是一名网络工程师,你正在为一家云计算公司开发一个虚拟机管理系统。你的系统需要为每个虚拟机分配一个唯一的ID,用来标识和通信。为了实现这个功能,你设计了一个管理ID的资源池,可以从资源池中分配资源ID和释放资源ID,分配方式有动态分配和指定分配。

动态分配是从资源池的开始分配一个资源ID,这种方式适用于新创建的虚拟机。指定分配是指定一个资源ID进行分配,这种方式适用于恢复或迁移的虚拟机。无论哪种分配方式释放资源ID时都需要放到资源池的尾部,这样可以保证资源ID的重用和均衡。

现在,你已经执行了一系列操作,你需要知道资源池的第一个空闲资源ID应该是多少,以便为下一个虚拟机分配。

注意:

资源池的初始顺序是从小到大。

资源池中空闲资源ID不足时,动态分配失败,对资源池不进行任何操作。指定分配资源ID已经被占用或者不在资源池范围内时,对资源池不进行任何操作。

释放资源ID不在资源池范围内时或者已经是空闲资源ID时,对资源池不进行任何操作。

保证每个用例最后都有空闲资源ID。

输入描述

输入第一行为两个整数 llrr ,表示资源池的范围;

输入第二行为一个整数 tt ,表示操作个数。

第三行开始,第一个数字代表操作类型 opop11 表示动态分配, 22 表示指定分配, 33 表示释放;

如果输入的第一个数字是 11 ,第二个表示分配的个数 numnum

如果输入的第一个数字是 22 ,第二个表示分配的资源ID;

如果输入的第一个数字是 33 ,第二个表示释放的资源ID。

1l<r1000001\le l\lt r \le 1000001t1000001\le t \le 100000

1op31\le op \le 31num2001\le num\le 200

输出描述

资源池的第一个空闲资源ID。

样例

样例一

输入

1 3
2
1 1
3 1

输出

2

样例解释

第一行资源池范围是 [1,3][1,3] ,资源池的初始顺序是 1>2>31->2->3

第二行操作个数有 22 个。

第三行动态分配 11 个资源ID,资源池中剩余的资源ID顺序是 2>32->3

第四行释放 11 个资源ID、资源ID是 11 ,资源池中剩余的资源ID顺序是 2>3>12->3->1

执行以上操作后,资源池的第一个空闲资源ID是 22

样例二

输入

1 3
3
2 2
3 2
1 1

输出

3

样例解释

第一行资源池范围是 [1,3][1,3] ,资源池的初始顺序是 1>2>31->2->3

第二行操作个数有 33 个。

第三行指定分配 11 个资源ID,资源ID是 22 ,资源池中剩余的资源ID顺序是 1>3>21->3->2

第四行释放 11 个资源ID,资源ID是 22 ,资源池中剩余的资源ID顺序是 1>3>21->3->2

第五行动态分配 11 个资源ID,分配的资源ID是 11 ,资源池中剩余的资源D顺序是 3>23->2

执行以上操作后,资源池的第一个空闲资源ID是 33