《編程之美》讀書筆記15： 4.5 磁帶文件存放優化
對一個已經是最優解的排列，記第i個文件的長度為Bi，被訪問概率為Ai。如果交換第i個和第i+1個文件，則平均長度一定不會變小，交換后，訪問原第i個文件時，要多訪問一個原第i+1文件，長度增加了Ai*Bi+1，而訪問原第i+1個文件時，要少訪問一個原第i個文件，長度減少了Ai+1*Bi，而訪問這兩個文件之前和之后的文件，長度沒有改變，故有：
Ai*Bi+1 - Ai+1*Bi >=0 即Ai/Bi >= Ai+1/Bi+1，
由于i可以任意取，因而A0/B0 >= A1/B1 >= A2/B2 >= … >= An-1/Bn-1。也就是說，最優解一定滿足P[i]/L[i] 按降序排列，而根據P[i]/L[i]值通過降序排列只能得到唯一確定的排列（只考慮P[i]/L[i]值大小，如果兩個文件的P[i]/L[i]值相同，它們位置可以互換而不影響），這個排列必然是最優解。因而，原問題等同于“將P[i]/L[i] 降序排列”。
類似題：
“將一個給定的自然數數組，連接起來得到一個數，求這個數的最大值或最小值”。