先看算導(dǎo)上輸油管道問題的描述：
這個(gè)題，雖然說給出了井的x,y坐標(biāo)，但是要修建的主管道卻只是一條橫向的，而且其余管道也只是到這條管道的豎向距離。
那么，就轉(zhuǎn)換為確定一條直線 y = m，使得其它個(gè)點(diǎn)到這條直線的距離最多。也許不需要多的提示，大家的直覺就會(huì)想到應(yīng)該
選所有y值的中點(diǎn)。但是，這個(gè)的證明卻不是那么的明顯。
證明如下：
設(shè)所有的y值系列為y1,y2,...,yn，并且假設(shè)這個(gè)是按遞增排列的。我們要求的是Sum =
Σ|yi-m|(1<=i<=n),
1）顯然假如選小于y1或者大于yn的y=m都不會(huì)比選y1或者yn更好。
2）如果選y1或者yn，那么|y1-m|+|yn-m| = |yn-y1|都是一樣的結(jié)果，甚至選y1和yn之間的任意一個(gè)值。
3）如此繼續(xù)下去，對(duì)于y2和yn，也有2）所描述的性質(zhì)
4）繼續(xù)到最后，只需要取最中間一對(duì)點(diǎn)之間的值即可，如果n是奇數(shù)，那么就是中間的點(diǎn)，如果n是偶數(shù)，取任意一個(gè)中間
點(diǎn)都可以。
通過上面證明，我們可以選取第y(n/2 + 1)作為修建主管道的地方。當(dāng)然這可能是唯一的最優(yōu)選擇，或者無數(shù)個(gè)最優(yōu)選擇中的一個(gè)。
那么現(xiàn)在已經(jīng)轉(zhuǎn)換為求中位數(shù)了，求中位數(shù)的辦法最簡單的是對(duì)序列排序然后取中間的即可。算法導(dǎo)論上有一種平均代價(jià)
O(n)的辦法，
思路類似于快速排序，快排的每一次操作都是劃分?jǐn)?shù)組，前小后大，如果我們也這一次次去劃分?jǐn)?shù)組，剛好軸元素處于我們要求的那個(gè)位置
上那么就達(dá)到我們的目的了，下面的代碼中
Select函數(shù)就是求一個(gè)數(shù)組的中位數(shù)。
對(duì)于POJ 1723題，很顯然y的選擇是中位數(shù)即可，x的選擇需要轉(zhuǎn)換一下也變成求中位數(shù)了。題目中描述，最后要達(dá)到的效果是每個(gè)士
兵都占成一橫排，而且彼此相鄰，也就是y相同，但是x系列是k,k+1,k+2,...,k+n-1。那么如何從原來的x0,x1,x2,...,x(n-1)移動(dòng)過去了。
可以簡單的考慮下，
將最左邊的士兵移動(dòng)到k,次左的移動(dòng)到k+1,...,最右邊的移動(dòng)到k+n-1，所需要的移動(dòng)之和一定是最小的。那么我們
可以將原來的x0-x(n-1)排序，得到x'0,x'1,...,x'(n-1),要求的
Sum = Σ|x'i - (k + i)| = Σ|(x'i - i) - k|,那么要使Sum最小，只需要
求序列X'i - i的中位數(shù)即可了。
代碼如下：
#include <stdio.h>
#include <stdlib.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;
}