先看算導上輸油管道問題的描述：
這個題，雖然說給出了井的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的中位數即可了。
代碼如下：
#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;
}