document.write('这道题的主要思路为：首先对请求按照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]由大到小的顺序来处理，请看下面的分析：
假设第一步处理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]从大到小排序处理请求，成功的可能性最大。如果按照这个序列都无
法完成请求序列，那么任何顺序都无法实现全部完成，实现代码如下：
def swap(arr,i,j):
tmp=arr[i]
arr[i]=arr[j]
arr[j]=tmp
#按照R[i]-O[i]由大到小进行排序
def bubbleSort(R,O):
lens=len(R)
i=0
while i＜lens-1:
j=lens-1
while j＞i:
if R[j]-O[j]＞R[j-1]-O[j-1]:
swap(R,j,j-1)
swap(O,j,j-1)
j-=1
i+=1
def schedule(R,O,M):
bubbleSort(R,O)
left=M #剩余可用的空间数
lens=len(R)
i=0
while i＜lens:
if left＜R[i]: #剩余的空间无法继续处理第i个请求
return False
else: #剩余的空间能继续处理第i个请求, 处理完成后将占用O[i]个空间
left-=O[i]
i+=1
return True
if __name__=="__main__":
R=[10,15,23,20,6,9,7,16]
O=[2,7,8,4,5,8,6,8]
N=8
M=50
scheduleResult=schedule(R,O,M)
if scheduleResult:
print "按照如下请求序列可以完成:"
i=0
while i＜N:
print str(R[i])+","+str(O[i])+" ",
i+=1
else:
print "无法完成调度"
程序的运行结果为：
按照如下请求序列可以完成：
20,4 23,8 10,2 15,7 16,8 6,5 9,8 7,6
算法性能分析：
这种方法的时间复杂度为O(N2)。
');