1.解题思路：本次大赛一等奖获得者-大连理工大学学生__newSolar，提供两种解题思路；
2.代码样本：雅虎刷题狂人曹鹏专家的代码将作为样本展示，供学习借鉴；
3."一起来找茬儿"：在所有答题者中，抽选部分未通过的错误代码，邀你来"找茬"；
题目描述：
在微软云计算服务的机房，有很多机器上跑着一个或者多个的虚拟机。在一段时间里，有很多用户会来请求建立虚拟机，或者把虚拟机关闭。这个时候，一个最重要的问题，是如何把用户的请求分配到不同的机器上。这里我们把实际的问题简化成对CPU的申请。
假定有M台机器用来服务用户，我们把机器编号成0到M。每台机器有多个CPU核，我们把核编号为0到Cm。
当用户在申请资源的时候，会生成一个请求 "申请<k>个核"，并且每个请求编号为m如果我们在现有的机器中能找到一台机器能满足，这台机器的空余的连续的核能满足要求的话，就返回<M, C>作为结果。M是机器的下标，C是申请的第一个核的下标。如果没有找到能满足请求的机器，<-1,
-1>作为结果。
当用户释放资源的时候，生成一个请求"第m个请求的资源释放"。保证一个请求释放最多一次。如果请求没有满足，忽略释放的请求。
输入
第一行是T, 总共的测试的个数
每个测试，第一行给出M 和Q，机器的总数和请求的个数
接下来是M行给出每一台机器的核数 Ci
接下来Q行给出请求。请求两种格式，
1. A k 表示申请k个核
2. F m 表示释放第m个请求申请的核
输出
对于每一个测试，首先输出
"Case #i:" i是测试的标号，从1开始。
接下来对于所有申请的请求，输出m c 或者-1
-1
[限制条件]
1 <= T <= 20
1 <= M <= 100000
1 <= Ci <= 128
1 <= Q <= 1000000
1 <= k <= 128
1 <= m <= M
The number of queries of type 1 is the same
as that of type 2.
题目解析：
考虑到数据范围，共有10W个机器，100W次查询，时间上不足以在每次询问中遍历所有的机器，但考虑到CPU的数量只有128
可以从这里入手加快查询效率。
解法一：
我们维护128个集合，每个集合存储不同的最长连续空闲核数的机器，(eg, 集合1存最长空闲数为1的机器，集合2存最长空闲数为2的机器）。对于每次A询问，申请核数为k，我们只需枚举从k到128的所有集合中机器编号最小的，为了查找效率，我们可以使用
c++STL的set (或者java的TreeSet), 内部是树形结构，每个集合的第一个元素即为最小元素，查找到之后暴力更新这个机器使用情况并把新的机器信息加入到集合中，同时为了F操作保存询问信息。对于F操作相对简单，直接恢复记录的信息并更新机器信息就可以了。
此方法每次询问的复杂度大约为O(128*log(n))。
解法二：
对于每次询问，我们直接从10W个机器下手，为了提高效率可以使用线段树，线段树的每个节点维护当前区间所有机器最长空闲数，对于A查询，申请核数为k，如果当前节点左儿子值>=k，则在左子树中查询，否则在右子树查询，可以很容易在log(n)时间内查询到所需要的机器。其他操作和上一种解法类似。
代码展示（解法一）：
http://student.csdn.net/mcd/topic/235300/937965
代码展示（解法二）：
http://student.csdn.net/mcd/topic/235300/937980
雅虎刷题狂人曹鹏专家代码展示：
http://student.csdn.net/mcd/topic/235300/937984
Read full article from 俱乐部编程挑战群话题-高校俱乐部
No comments:
Post a Comment