目录

1. 报数游戏
2. 宝藏勘探
3. 心智能力
4. 牌型分组
5. 资源分配

1. 报数游戏

一群同学围着一圈坐，编号 $1$ 到 $n$ ，给定 $m$ ，从第一个同学开始报数开始报 $m$ 个后，第 $m$ 位同学离场，从圆圈中离开，剩余同学继续每隔 $m$ 个报数离场一个人，问最后剩余的那个同学编号是多少。

完了，我记得这题之前还在哪个博客见过，还是什么 B 站视频看过，这题是有对应的数学公式解法的，但是我忘记了，只能试试暴力方法，不过一看数据范围最大 1000 ，好家伙，这不打卡题嚒，直接暴力 AC。vector 配合迭代器每次删除一个，然后在新的剩余人数中求模得到新下标，对于容器来说，有了下标等价于有了迭代器位置，有了迭代器就可以删除元素，不用自己处理。

2. 宝藏勘探

在一个从 $0$ 到 $n$ 的数轴上，每个位置有一个宝藏辐射值。两位勘探员正在勘探宝藏，勘探过的位置中的最大值和最小值之差代表整块数轴地的辐射值，能反映这块地方的宝藏可能性。两位勘探员分别从数轴的两侧相向而行，但是他们之间有矛盾，不愿意隔得太近，两位勘探员中间只剩 $k$ 个单位长度时，就会停止前进。目前不知道两位勘探员谁先出发，只知道他们各自从两端相向而行向中间靠拢，中间相隔 $k$ 个位置的时候停止勘探。问这块数轴地可能最小的宝藏辐射值是多少？

题目的意思很明确了，也即从左往右 + 从右往左各来一次最大值最小值前后缀计算，求每个位置其左侧和右侧的前缀/后缀最大最小值，然后中间隔 $k$ 个位置，用左右两侧的最小值作为实际最小值，左右两侧的最大值作为实际最大值，此时计算一次最大值减去最小值并维护更新答案。滑窗一遍即可计算出来。

比如前缀 $[0,x]$ 的最小值和后缀 $[x+k+1,n]$ 的最小值，取其小者；前缀 $[0,x]$ 和后缀 $[x+k+1,n]$ 的最大值取其大者。此时就是一种勘探员互相停止的情况，计算这种情况下的辐射值，维护更新一次答案，然后把中间这块长度为 $k$ 的禁区滑窗右移，再次通过两侧取最大最小值计算辐射差值，继续维护更新，直到滑窗完成。

3. 心智能力

小明小红两个人进行记忆和心算能力测试，两个人各自脑海中有一个初始化为全零长度为 $n$ 的数组，互相对对方的某个指定区间做加减修改（不会是差分数组或者线段树吧？），但是发现太容易了，于是加大难度。现在对对方的某个区间进行统一增加/减少修改时，需要指定对值为奇数还是偶数的值做操作（注意不是下标的奇偶性，而是值的奇偶性），小明觉得有点难度了，请你帮他设计一个程序完成小红的挑战。

寄，没思路，感觉线段树也用不上了，差分数组或者前缀和也不是，都试过了全部超时，感觉应该是有其他正确的解法，或者我没见过的数据结构。一开始写的暴力方法，一个数组额外记录每个位置上值的奇偶性，然后操作的时候，根据奇偶数的加法更新区间内每个值的奇偶性，同时只有奇偶性匹配的值才会做修改。这里我用位运算稍微优化了一下，不过也就优化了几百毫秒，我的方案整体用时 11 秒，优化微不足道。位运算优化就是异或来更新奇偶性，毕竟异或的话 同为零，异为一 ，同时奇偶数加减法又有以下规律：

1. 奇数 与 奇数 得 偶数
2. 奇数 与 偶数 得 奇数
3. 偶数 与 奇数 得 奇数
4. 偶数 与 偶数 得 偶数

，现在我们要让这个性质成为加法的乘一系数（也就是 $a+b\times [0|1]$ ），这样就不用写 if-else 语句特判哪个元素符合操作的奇偶性了，毕竟 if-else 分支预测语句是很影响 CPU 的指令吞吐率的，能不用分支结构尽量不用分支结构。因此这里的需求是性质相同则系数为 $1$ ，性质不同则系数为 $0$ ，代表无效操作。那么还是可以用异或的，只不过变成了 同为一，异为零 罢了（题目中 $1$ 表示奇数操作，$0$ 表示偶数操作，我的奇偶性数组就顺便和题目统一表示了吧），所以就是 $1-a\oplus b$ 反转一下即可。 当然最后还是超时，没有拿到分，寄。

4. 牌型分组

给定一副扑克牌，牌型分组的时候无需考虑花色。普通扑克牌一组 13 张，这里可以拓展为更普适的情况， $n=x$ ，其中 $x$ 可能到 500。扑克牌的每张牌有牌点，除了大小王，牌点最大的牌是 2，然后是 $A$ ，然后是 $[n,\dots ,3]$ 。可以考虑的牌型如下

1. 单张
2. 对子（牌点相同的两张牌）
3. 三张（牌点相同的三张牌）
4. 顺子（牌点相同的五张牌）

其中对于顺子来说有一些特殊要求：

1. 不能出现 $[\dots ,2,A,\dots ]$ 的顺子，也就出顺子牌的时候 $2$ 不能作为 $A$ 的下一张
2. 可以使用 $[5,4,3,2,A]$ 顺子

尽可能地组多张牌的牌型打出去，求最后剩余的牌点严格比 $A$ 小的单张牌数量。每行测试用例会包含一张牌的花色和牌点，用空格分离（花色没啥用吧其实？还是说我漏看了什么信息），大小王牌同样不设数量限制（大小王牌应该是只能通过三张和对子出掉了）。

没思路，没做出来，感觉是个大模拟题。但是也有一点规律，首先应该是要贪心的，$2、3、5$ 这三个数互质啊，是不是这三个牌型各自组各自的不怎么影响。那是不是能出顺子就出顺子，出完顺子再考虑三张，最后考虑对子，实在没有了就是出完了只剩单张了，不知道这个贪心思路对不对。

5. 资源分配

初始给定一组逻辑处理器数量和物理内存固定的物理机，现在要处理客户创建虚拟机的资源分配需求，要求实现：

1. init(n, c, m) 表示初始化 $n$ 台具有 $c$ 个逻辑处理器以及 $m$ GB 物理内存的物理机
2. create(vid, vcpu, vmem) ，表示需要在有可用资源的物理机上创建一个虚拟机ID为 vid 的，需要 vcpu 个逻辑处理器以及 vmem GB 物理内存的虚拟机，如果资源不够（没有任何一台物理机的剩余量能够同时满足 cpu 和 mem 的需求），可以申请立刻扩容一台物理机加入到资源池再继续分配（所有物理机规格相同，和初始化时候的机器配置一样），返回值是一个二元组，表示虚拟机实际被分配到的物理机编号和是否扩容了一台物理机（题目说一次性最多可以扩容 500 台物理机，但是又强调一次虚拟机分配的资源不可能超过单台物理机的配置，那不就肯定每次最多扩容一台嚒，没懂，可能是混淆视听？）
3. remove(vid) ，删除虚拟机ID为 vid 的虚拟机，将计算资源归还给对应的物理机

请使用尽可能少的物理机完成每个测试用例的虚拟机分配创建请求，测试数据给定一个已经实现的虚拟机分配算法作为基线算法，它在公开的 20 个测试样例中已经给出了由 baseline 分配算法通过测试样例所有虚拟机分配的最少的物理机数量，你的分配算法如果比 baseline 强可以得到额外的加分，加分是乘法系数，系数为 $\frac{base}{your}$ ，也即你给出的所需物理机数量比 base 给出的数量越少，奖励倍数越大，最终本题得分由所有测试样例的平均分决定，满分 200 分。

物理机最多创建 $5\times 10^5$ 台（忘记是不是这个数了，反正很大，测试样例实际运行出来的结果也很大）。每次申请的虚拟机的资源需求一定不会超过物理机的单机配置，也就是不会出现多台物理机的计算资源融合供给给一台虚拟机使用（大大降低了难度）。如果你的分配算法导致系统 OJ 检测到不合理的分配，比如在已经资源耗竭的物理机上继续分配虚拟机，测试会立即终止，并且该测试样例不得分。

其实类似 leetcode ，不过这里是一个完整的离线项目，需要本地 IDE 有多文件编译经验才行，我是本地随手写了个简陋的 CMakeLists 编译的。用户要求实现 Scheduler.cpp 文件中空白的函数体定义，配合 main.cpp 文件进行 benchmark 测试，离线的 20 个公开测试样例已经作为文本文件放在 data 目录下，main.cpp 运行时自动读取测试样例和基线答案，无需用户关心 IO ，用户只需要实现 Scheduler.cpp 在通过本地测试之后把 Scheduler.cpp 的内容粘贴到提交窗口提交评分即可。（不是，怎么这么一股国外数据库公开课 15445 味道啊，还要自己填充空的函数体交上去评分排名 rank ？）

有几种参考的思路：

1. 直接爽开最大数量的物理机，来分配的虚拟机需求直接顺序分配物理机，爽。就是这么干基本是零分，因为得分系数是基线给出的最少需要的物理机数量和你的分配算法给出的物理机数量之比，你的数量要是太大了那 base 分子就会相对的很小。每题的基线分是 120
2. 对资源池里面的物理机用 for-loop ，找到合适的物理机就分配资源，没有就扩容一台
3. 使用操作系统级的资源分配算法，比如内存池中碎片最小的适应性分配算法，或者页面分配算法中的优先级队列，看你做到这题还剩多少时间。我选了个比较简单的二分优化找到第一台有至少满足资源的机器的方案

我觉得我的这种 FirstFit 方案就是基线方案，因为我交上去评分就是 120 分，和基线差不多，满分 200 分的方案肯定是用了什么数据结构的，有优先级的分配。

这题二分的话要注意，是基于两个指标来二分，cpu 和 mem ，因为平时 leetcode 写二分都是基于一个指标来写的，所以还折腾了一会（没搞懂具体原理，但反正工作结果是符合预期了，二分查找停止的位置能在两个资源指标都符合的时候才停止）。另外还需要考虑具体实现上存放物理机资源池的数据结构，物理机本身的 CPU 和 MEM 很简单，搞个结构体放两个 int 字段表示物理机的剩余资源就行，关键就是这个结构体在什么数据结构中，插入的时候自动就是按照 CPU 和 MEM 排序的。一开始我想用优先队列，发现优先队列是适配器不是容器，没有 begin() 和 end() 迭代器，没法从数据结构中删除旧的物理机状态再插入新的物理机状态，所以放弃了。然后想到可以用 multiset ，可重复的集合中，元素是有序插入的，时间复杂度应该是 $O(nlogn)$ ，还能接受，查找删除定位的话，只需要每次在申请物理机的时候把物理机编号和插入 emplace 返回的迭代器记录在哈希表里面就行了，要修改物理机的状态的时候，直接从哈希表拿到迭代器把物理机状态从 multiset 里面拎出来（multiset.erase 删除掉旧状态），做完物理机资源的增加/减少再重新把状态插入回 multiset 排序。

multiset 因为有迭代器可以顺序遍历，因此是可以二分的，直接使用标准库 <algorithmn> 提供的 std::lower_bound 即可找到第一个资源大于等于虚拟机要求的物理机。但是 std::lower_bound 最好自己提供一个 lambda 比较函数，一次就定位到 cpu 和 mem 资源都符合的物理机上，如果是默认的 pair<int, int> 之类的什么二元组比较，可能第一个 cpu 资源满足了就停止查找了，然后你还得从停止的位置自己做线性 iter++ 往后找 mem 符合要求的物理机，也是很慢的。

其他细节的话就是还要保存虚拟机分配到哪个物理机的哈希表映射，这样 remove(vid) 的时候你才能根据 vid 找到对应的物理机 pid 去 multiset 里拿到状态。然后物理机资源状态是自定义结构体 struct 记得要开一个对应的结构体重载 operator() 作为比较运算子给 multiset 的模板参数，比如 std::multiset<type_rs, type_comp> ，其中 type_comp 是重载了 operator()(const type&, const type&) 负责比较两个物理机状态结构体的结构体。

create 的思路就是：

1. 二分查找
2. 迭代器指向末尾，没有合适的空闲机器，申请一台新的并把当前虚拟机分配到新的物理机上
3. 迭代器指向有效位置，有合适的空闲机器，删除空闲物理机的旧状态，更新物理机分配资源给虚拟机，剩余资源减少的新状态，重新插入到 multiset
4. 更新 “物理机-迭代器” 和 “虚拟机ID-物理机ID” 的哈希表映射

remove 的思路就是：

1. 根据虚拟机ID得到物理机ID
2. 删除物理机旧状态，更新物理机剩余资源得到新状态，新状态重新插入回 multiset
3. 更新 “物理机-迭代器” 和 “虚拟机ID-物理机ID” 的哈希表映射