先看算导上输油管道问题的描述：
![]()
这个题，虽然说给出了井的x,y坐标，但是要修建的主管道却只是一条横向的，而且其余管道也只是到这条管道的竖向距离。那么，就转换为确定一条直线 y = m，使得其它个点到这条直线的距离最多。也许不需要多的提示，大家的直觉就会想到应该所有y值的中点。但是，这个的证明却不是那么的明显。
证明如下：
设所有的y值系列为y1,y2,…,yn，并且假设这个是按递增排列的。我们要求的是Sum = Σ|yi-m|(1<=i<=n),
1）显然假如选小于y1或者大于yn的y=m都不会比选y1或者yn更好。
2）如果选y1或者yn，那么|y1-m|+|yn-m| = |yn-y1|都是一样的结果，甚至选y1和yn之间的任意一个值。
3）如此继续下去，对于y2和yn，也有2）所描述的性质
4）继续到最后，只需要取最中间一对点之间的值即可，如果n是奇数，那么就是中间的点，如果n是偶数，取任意一个中间点都可以。
通过上面证明，我们可以选取第y(n/2 + 1)作为修建主管道的地方。当然这可能是唯一的最优选择，或者无数个最优选择中的一个。那么现在已经转换为求中位数了，求中位数的办法最简单的是对序列排序然后取中间的即可。算法导论上有一种平均代价O(n)的办法，思路类似于快速排序，快排的每一次操作都是划分数组，前小后大，如果我们也这一次次去划分数组，刚好轴元素处于我们要求的那个位置上那么就达到我们的目的了，下面的代码中Select函数就是求一个数组的中位数。
对于POJ 1723题，很显然y的选择是中位数即可，x的选择需要转换一下也变成求中位数了。题目中描述，最后要达到的效果是每个士兵都占成一横排，而且彼此相邻，也就是y相同，但是x系列k,k+1,k+2,…,k+n-1。那么如何从原来的x0,x1,x2,…,x(n-1)移动过去了。可以简单的考虑下，将最左边的士兵移动到k,次左的移动到k+1,…,最右边的移动到k+n-1，所需要的移动之和一定是最小的。那么我们可以将原来的x0-x(n-1)排序，得到x’0,x’1,…,x’(n-1),要求的Sum = **Σ|x’i - (k + i)| = Σ|(x’i - i) - k|**,那么要使Sum最小，只需要求序列X’i - i的中位数即可了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| #include <stdio.h>
#include <algorithm>
using std::sort;
using std::swap;
#define MAX (10000 + 10)
int Partion(int* pnA, int nLen)
{
int i, j;
for (i = j = 0; i < nLen - 1; ++i)
{
if (pnA[i] < pnA[nLen - 1]) { swap(pnA[i], pnA[j++]); } } swap(pnA[j], pnA[nLen - 1]); return j; } int Select(int* pnA, int nLen, int nIndex) { if (nLen > 1)
{
int nP = Partion(pnA, nLen);
if (nP + 1 == nIndex)
{
return pnA[nP];
}
else if (nP + 1 > nIndex)
{
return Select(pnA, nP, nIndex);
}
else
{
return Select(pnA + nP + 1, nLen - nP - 1, nIndex - nP - 1);
}
}
else
{
return pnA[0];
}
}
int main()
{
int nX[MAX];
int nY[MAX];
int nN;
int i;
while (scanf("%d", &nN) == 1)
{
for (i = 0; i < nN; ++i)
{
scanf("%d%d", &nX[i], &nY[i]);
}
int nMY = Select(nY, nN, nN / 2 + 1);
sort(nX, nX + nN);
for (i = 0; i < nN; ++i)
{
nX[i] = nX[i] - i;
}
int nMX = Select(nX, nN, nN / 2 + 1);
int nSum = 0;
for (i = 0; i < nN; ++i)
{
nSum += abs(nX[i] - nMX);
nSum += abs(nY[i] - nMY);
}
printf("%d\n", nSum);
}
return 0;
}
|
