如何对磁盘进行分区：教你一招

【出自XM面题】

难度系数：★★★★☆ 被考察系数：★★★★☆

题目描述：

有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；对于每个分区，从上次分配的磁盘开始继续分配，如果没有足够的空间，则顺序找其他的磁盘，直到找到合适的磁盘为止，进行分配；如果找不到合适的磁盘，则分配失败，实现代码如下：(www.xing528.com)

程序的运行结果如下：

分配成功

算法性能分析：

这种方法使用了双重循环，因此，时间复杂度为O（MN）。