判断请求在给定存储条件下是否能完成

【出自BD笔试题】

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

题目描述：

给定一台有m个存储空间的机器，有n个请求需要在这台机器上运行，第i个请求计算时需要占R[i]空间，计算结果需要占O[i]个空间（O[i]＜R[i]）。请设计一个算法，判断这n个请求能否全部完成？若能，给出这n个请求的安排顺序。

分析与解答：

这道题的主要思路为：首先对请求按照R[i]-O[i]由大到小进行排序，然后按照由大到小的顺序进行处理，如果按照这个顺序能处理完，则这n个请求能被处理完，否则处理不完。那么请求i能完成的条件是什么呢？在处理请求i的时候前面所有的请求都已经处理完成，那么它们所占的存储空间为O（0）+O（1）+…+O（i-1），那么剩余的存储空间left为left=m-（O（0）+O（1）+…+O（i-1）），要使请求i能被处理，则必须满足left＞=R[i]，只要剩余的存储空间能存放的下R[i]，那么在请求处理完成后就可以删除请求从而把处理的结果放到存储空间中，由于O[i]＜R[i]，此时必定有空间存放O[i]。

至于为什么用R[i]-O[i]由大到小的顺序来处理，请看下面的分析：(www.xing528.com)

假设第一步处理R[i]-O[i]最大的值。使用归纳法（假设每一步都取剩余请求中R[i]-O[i]最大的值进行处理），假设n=k时能处理完成，那么当n=k+1时，由于前k个请求是按照R[i]-O[i]从大到小排序的，在处理第k+1个请求时，此时需要的空间为A=O[1]+...+O[i]+...+O[k]+R[k+1]，只有A＜=m的时候才能处理第k+1个请求。假设我们把第k+1个请求和前面的某个请求i换换位置，即不按照R[i]-O[i]由大到小的顺序来处理，在这种情况下，第k+1个请求已经被处理完成，接着要处理第i的请求，此时需要的空间为B=O[1]+...+O[i-1]+O[k+1]+O[i+1]+...+R[i]，如果B＞A，则说明按顺序处理成功的可能性更大（越往后处理剩余的空间越小，请求需要的空间越小越好）；如果B＜A，则说明不按顺序更好。根据R[i]-O[i]有序的特点可知：R[i]-O[i]＞=R[k+1]-O[k+1]，即O[k+1]+R[i]＞=O[i]+R[k+1]，所以，B＞=A，因此，可以得出结论：方案B不会比方案A更好。即方案A是最好的方案，也就是说按照R[i]-O[i]从大到小排序处理请求，成功的可能性最大。如果按照这个序列都无法完成请求序列，那么任何顺序都无法实现全部完成，实现代码如下：

程序的运行结果为：

按照如下请求序列可以完成：

20，4 23，8 10，2 15，7 16，8 6，5 9，8 7，6

算法性能分析：

这种方法的时间复杂度为O（N²）。