学步园

《编程之美》读书笔记15： 4.5 磁带文件存放优化

 

对一个已经是最优解的排列，记第i个文件的长度为B_i，被访问概率为A_i。如果交换第i个和第i+1个文件，则平均长度一定不会变小，交换后，访问原第i个文件时，要多访问一个原第i+1文件，长度增加了A_i*B_i+1，而访问原第i+1个文件时，要少访问一个原第i个文件，长度减少了A_i+1*B_i，而访问这两个文件之前和之后的文件，长度没有改变，故有：

A_i*B_i+1 - A_i+1*B_i >=0 即A_i/B_i >= A_i+1/B_i+1，

由于i可以任意取，因而A₀/B₀ >= A₁/B₁ >= A₂/B₂ >= … >= A_n-1/B_n-1。也就是说，最优解一定满足P[i]/L[i] 按降序排列，而根据P[i]/L[i]值通过降序排列只能得到唯一确定的排列（只考虑P[i]/L[i]值大小，如果两个文件的P[i]/L[i]值相同，它们位置可以互换而不影响），这个排列必然是最优解。因而，原问题等同于“将P[i]/L[i] 降序排列”。

 

 

类似题：

“将一个给定的自然数数组，连接起来得到一个数，求这个数的最大值或最小值”。