某島

… : "…アッカリ~ン . .. . " .. .
January 20, 2013

POJ 3666. Making the Grade

http://acm.hust.edu.cn:8080/judge/problem/viewProblem.action?id=10721

Brief description:

給定一個整數序列 {an} 求一個不降序列 {bn},最小化 {an} 和 {bn} 各項差絕對值之和:
S = |a1 – b1| + |a2 – b2| + … + |an – bn|。

Analysis:

演算法 1:動態規劃(2D/0D。。
。。f[i][j]: 當前考察到 ai,最後一個 bi 為 a[o[j]]。(其中 o 數字 為 a 數組排序後每個名次所對應的下標。

http://acm.hust.edu.cn:8080/judge/problem/viewSource.action?id=901783

演算法 2:可合併堆。

我們先來看看兩個最特殊的情況:

  1. a[1]≤a[2]≤…≤a[n],在這種情況下,顯然最優解為 b[i] = a[i];
  2. a[1]≥a[2]≥…≥a[n],這時,最優解為 b[i] = x,其中 x 是數列 a 的中位數 。

於是我們可以初步建立起這樣一個思路:
把 1 … n 劃分成 m 個區間:[q[1], q[2]),[q[2], q[3]),……,[q[m], q[m+1]) 。每個區間對應一個解,b[q[i]] = b[q[i]+1] = … = b[q[i+1]-1] = w[i],其中 w[i] 為 a[q[i]], a[q[i]+1], … , a[q[i+1]-1] 的中位數。
顯然,在上面第一種情況下 m=n,q[i]=i;在第二種情況下 m=1,q[1]=1。
這樣的想法究竟對不對呢?應該怎樣實現?

若某序列前半部分 a[1], a[2], … , a[m-1] 的最優解為 (u,u,…,u),後半部分a[m], a[n+2], … , a[n] 的最優解為 (v,v,…,v),那麼整個序列的最優解是什麼呢?
若 u ≤ v,顯然整個序列的最優解為 (u,u,…,u,v,v,…,v)。否則,設整個序列的最優解為 (b[1],…,b[m],b[m+1],…,b[n]),則顯然 b[m] ≤ u
(否則我們把前半部分的解 (b[1],b[2],…,b[m-1]) 改為 (u,u,…,u),由題設知整個序列的解不會變壞),同理 b[m+1] ≥ v。
接下來,我們將看到下面這個事實:
對於任意一個序列 a[1],a[2],…,a[n],如果最優解為 (u,u,…,u),那麼在滿足 u≤u′≤b[1] 或 b[n]≤u′≤u 的情況下,(b[1],b[2],…,b[n]) 不會比 (u′,u′,…,u′) 更優。

我們用歸納法證明u≤u′≤b[1] 的情況,b[n]≤u′≤u的情況可以類似證明。
當n=1時,u=a[1],命題顯然成立。
當n>1時,假設對於任意長度小於n的序列命題都成立,現在證明對於長度為n的序列命題也成立。首先把 (b[1], b[2], … b[n]) 改為 (b[1], b[1], … b[1]),這一改動將不會導致解變壞,因為如果解變壞了,由歸納假設可知a[2],a[3],…,a[n]的中位數w>u,這樣的話,最優解就應該為(u,u,…,u,w,w,…,w),矛盾。然後我們再把(b[1],b[1],…,b[1])改為 (u′,u′,…,u′),由於| a[1] – x | + | a[2] – x | + … + | a[n] – x | 的幾何意義為數軸上點x到點a[1], a[2], … a[n]的距離之和,且u≤u′≤b[1],顯然點u′到各點的距離之和不會比點b[1]到各點的距離之和大,也就是說,(b[1],b[1],…,b[n]) 不會比 (v,v,…,v) 更優。(證畢)
再回到之前的論述,由於b[n]≤u,作為上述事實的結論,我們可以得知,將(b[1],b[2],…,b[n])改為(b[n],b[n],…,b[n]),再將(b[n+1],b[n+2],…,b[m])改為(b[n+1],b[n+1],…,b[n+1]),並不會使解變壞。也就是說,整個序列的最優解為(b[n],b[n],…,b[n],b[n+1],b[n+1],…,b[n+1])。再考慮一下該解的幾何意義,設整個序列的中位數為w,則顯然令b[n]=b[n+1]=w將得到整個序列的最優解,即最優解為 (w,w,…,w)。
分析到這裡,我們一開始的想法已經有了理論依據,演算法也不難構思了。

—— 引自 《左偏樹的特點及其應用》,黃源河

左偏樹。。

演算法 3:劃分樹。
(。。Orz。

External link:

http://blog.163.com/hacker_james/blog/static/659024432011711105241183/