论述题 3.  有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.1201],分区为[60,60,80,20,80]可分配,如果为[60,80,80,20,80],则分配失败。
【正确答案】本题的主要思路如下:对所有的分区进行遍历,同时用一个变量dIndex记录上次分配磁盘的下标,初始化为0;对于每个分区,从上次分配的磁盘开始继续分配,如果没有足够的空间,则顺序找其他的磁盘,直到找到合适的磁盘为止,进行分配;如果找不到合适的磁盘,则分配失败,实现代码如下:
   public class Test{
   public static void main(String[]args){
   int[]d={120,120,120};//磁盘
   int[]p={60,60,80,20,80};//分区
   if(is_allocable(d,p)){
   System.out.println("分配成功");
   }else{
   System.out.println("分配失败");
   }
   }
   private static boolean is_allocable(int[]d,int[]p)    {
   int dIndex=0;//磁盘分区下标
   for(int i=0;i<p.length;i++){
   //找到符合条件的磁盘
   while(dIndex<d.length&&p[i]>d[dIndex])
   dIndex++;
   //没有可用的磁盘
   if(dIndex>=d.length)
   return false;
   //给分区分配磁盘
   d[dIndex]-=p[i];
   }
   return true;
   }
   }
   程序的运行结果为:
   分配成功
【答案解析】