某岛

… : "…アッカリ~ン . .. . " .. .
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/