雁過無痕

《編程之美》讀書筆記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] 降序排列”。

類似題：

“將一個給定的自然數數組，連接起來得到一個數，求這個數的最大值或最小值”。