问答题
6. 有N个磁盘，每个磁盘大小为D[i](i=0...N-1)，现在要在这N个磁盘上”顺序分配”M个分区，每个分区大小为P[j](j=0…M-1)，顺序分配的意思是：分配一个分区P[j]时，如果当前磁盘剩余空间足够，则在当前磁盘分配；如果不够，则尝试下一个磁盘，直到找到一个磁盘D[i+k]可以容纳该分区，分配下一个分区P[j+1]时，则从当前磁盘D[i+k]的剩余空间开始分配，不在使用D[i+k]之前磁盘末分配的空间，如果这M个分区不能在这N个磁盘完全分配，则认为分配失败，请实现函数，is allocable判断给定N个磁盘(数组D)和M个分区(数组P)，是否会出现分配失败的情况?举例：磁盘为[120,120,120]，分区为[60,60,80,20,80]可分配，如果为[60,80,80,20,80]，则分配失败。
【正确答案】本题的主要思路如下：对所有的分区进行遍历，同时用一个变量dIndex记录上次分配磁盘的下标，初始化为0；对于每个分区，从上次分配的磁盘开始继续分配，如果没有足够的空间，则顺序找其他的磁盘，直到找到合适的磁盘为止，进行分配；如果找不到合适的磁盘，则分配失败，实现代码如下：
def is_allocable(d,p):
dIndex=0 #磁盘分区下标
i=0
while i＜len(p):
#找到符合条件的磁盘
while dIndex＜len(d) andp[i]＞d[dIndex]:
dIndex+=1
#没有可用的磁盘
if dIndex＞=len(d):
return False
#给分区分配磁盘
d[dIndex]-=p[i]
i+=1
return True
if __name__=="__main__":
d=[120,120,120] #磁盘
p=[60,60,80,20,80] #分区
if is_allocable(d,p):
print "分配成功"
else:
print "分配失败"
程序的运行结果为：
分配成功
算法性能分析：
这种方法使用了双重循环，因此，时间复杂度为O(MN)。
【答案解析】[考点] 如何对磁盘分区