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：可合并堆。
我们先来看看两个最特殊的情况：
- a[1]≤a[2]≤…≤a[n]，在这种情况下，显然最优解为 b[i] = a[i]；
- 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/
