分治算法--⼠兵排队（poj1723）
【问题描述】
在⼀个划分成⽹格的操场上，n 个⼠兵散乱地站在⽹格点上。⽹格点由整数最表(x,y)表⽰。⼠兵可以沿着⽹格边上、下、左、右移动⼀步，但在同⼀时刻⼀个⽹格上只能有⼀名⼠兵。按照军官的命令，⼠兵们要整齐地列成⼀个⽔平队列，即排列成(x,y),(x+1,y),…,(x+n-1,y)。如何选择x,y 的值，才能使⼠兵们以最少的总移动步数排成⼀列。
请计算使所有⼠兵排成⼀⾏需要的最少移动步数。
【输⼊格式】
第1⾏是⼠兵总数n 。接下来的n ⾏是⼠兵的初始位置，每⾏两个整数x 和y 。
【输出格式】
cstring转为int输出⼠兵排成⼀⾏需要的最少移动步数。
【输⼊样例】【输出样例】【数据范围】
1<=n<=10000
-10000<=x,y<=10000
问题分析：
通过适当的移动顺序和移动路线可以使得同⼀时刻不会有两名⼠兵站在同⼀点。
题⽬要求移动的最少步数
题⽬要求可转化为求⼠兵站⽴的“最终位置”，即如何取“最终位置”使得⼠兵移动的步数最少
1. Y轴⽅向上的考虑(出Y0的值)
设⽬标坐标为Y0，即n个⼠兵最终需要移动到的Y轴的坐标值为M
n个⼠兵的Y轴坐标分别为：
Y1，Y2 …… …… Yn
移动步数
S=|Y1-Y0|+|Y2-Y0|+ …… …… +|Yn-Y0|
结论：Y0取所有Yi的中间值时可以使得S达到最⼩。
(可以证明）
中位数是Y0;
解决办法：
1.对所有的Y轴坐标进⾏排序（O（nlogn））或者进⾏线性时间选择（O（n））然后取“中间”点的Y轴坐标值作为最佳位置Y0的值
2.通过公式求出Y轴⽅向上移动的最优步数
51 22 21 33 -23 3
1
2
3
4
5
68
1
2. X轴⽅向上的考虑
（1）⾸先需要对所有⼠兵的X轴坐标值进⾏排序
（2）然后，按从左⾄右的顺序依次移动到每个⼠兵所对应的“最终位置”（最优），所移动的步数总和就是X轴⽅向上需要移动的步数  设排序后n个⼠兵在X轴坐标为：
X1’，X2’ …… …… Xn’
他们最终位置”的X轴坐标值为：
X0，X0+1，X0+2 …… …… X0+（n-1）
则所求移动的步数
S=|X1’-X0| + |X2’-(X0+1)|+ …… +|Xn’-(X0+(n-1)|
经过变形
S=|X1’-X0|+ |(X2’-1)-X0|+ …… +|(Xn’-(n-1))-X0|
注意到公式的形式与Y轴⽅向上的考虑⼀样，同样是n个已知数分别减去⼀个待定数后取绝对值，然后求和
问题转化为：
求出x1’,x2’-1,…Xn’-(n-1)的中位数，即求得X0值，最后算出最优解。
中位数寻的快速算法
⼀般寻中位数可以先将数组排序，按照次序将中间的数据作为中位数即可，其时间复杂度主要取决于排序算法的时间复杂度，利⽤快速排序可以将其控制为线性对数量级。
但是能否打破线性对数的限制呢？其中最关键的问题是，寻中位数并不需要整个数组完全有序，如果把多余的元素排序省略掉，那么就可以超越线性对数的限制实现最快的算法。
启发来源于快速排序算法中的切分法，⽐如我们需要到数组中第 k⼩的元素，⾸先将数组a[lo,hi]切分返回整数j，使得a[lo,j-1]都⼩于等于a[j]，⽽a[j+1,hi]都⼤于等于a[j]，如果j==k，那么j位置的元素就是我们要的第k⼩的元素，⽽如果j>k，就要切分左⼦数组，如果j<k，就要切分右⼦数组，不断缩⼩选定的⼦数组的规模直到只剩下⼀个元素，则它就是最终我们要的第k⼩的元素。
经过数学推导，这种快速切分法寻中位数仅仅为线性量级，是寻中位数最为快速的算法。
int partition(int *a,  int low, int high)
//分治算法中的分
{  int X0ey = a[low];
while(low<high)
{  while(low < high && a[high] >= X0ey)
high--;
a[low] = a[high];
while(low<high && a[low] <= X0ey)
low++;
a[high]=a[low];
}
a[low]=X0ey;
return low;
}
// 出数组中第k⼩的元素，⾮递归实现
int select1(int *a, int k,int n) {
int lo = 0;
int lo = 0;
int hi = n-1;
//到最⼩的开始元素，以及终点元素；
while (hi > lo) {
int j = partition(a, lo, hi);//先是进⾏分的思想；返回每⼀轮中已经排好的数的位置；从0开始；
if(j == k){//如果已经排好的数的位置的数刚好是第k⼩的数；就直接返回，
return a[k];
}
else if(j > k) {//如果是已经排好数的位置坐标⼤于k，表⽰将从⼤的⼀边继续进⾏查；
hi = j - 1;
}
else if(j < k) {//如果是已经排好数的位置坐标⼩于k，表⽰将从⼩的⼀边继续进⾏查；
lo = j + 1;
}
}
return a[k];
}
// 出数组中第
int select2(int a[], int k, int lo, int hi) {
int j = partition(a, lo, hi);
if (j == k) {
return a[k];
} else if (j > k) {
return select2(a, k, lo, j - 1);
} else {
return select2(a, k, j + 1, hi);
}
}
int main()
{
int a[10] = {2,1,3,4,7,9,8,10,5,11};
cout<<select1(a, 9,10)<<endl;
cout<<select2(a, 9,0,9)<<endl;
return 0;
}
题⽬代码：
这是没⽤上⾯的中位数的⽅法写的，在poj上能过，不过时间稍稍有点长；
#include <iostream>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
#define NUM 10001
using namespace std;
int com(const void *a,const void *b)
{
return *((int*)a)-*((int*)b);//从⼩到⼤
}
int main() {
int N,X[NUM],Y[NUM];//存放x和y坐标
cin>>N;//表⽰⼠兵数
for ( int i = 0; i<N;i++){
cin>>X[i]>>Y[i];
}//输⼊操作
//⼠兵移动x坐标或者是y坐标移动⼀个单位，在poj上提交可以不⽤这个功能；    for( int i = 0 ; i<N;i++){
int dirction =0+ rand()%(int)(1-0+1);//移动的坐标
int move = (-1)+rand()%(int)(1-(-1)+1);//移动⽅向
if(dirction == 0){
int x = X[i] + move;
int j = 0;
for(j = 0; j<N;j++){
if(x!=X[j]&&Y[i]!=Y[j])//有相同的坐标就不需移动
continue ;
else
break;
}
if(j == N)
X[i] = x;
}
//移动x坐标
else if(dirction == 1){
int y = Y[i] + move;
int j = 0;
for(j = 0; j<N;j++){
if(y!=Y[j] &&X[i]!=X[j])//有相同的坐标就不需移动
continue ;
else
break;
}
if(j == N)
Y[i] = y;
}//移动y坐标
}
qsort(Y, N, sizeof(int), com);
qsort(X, N, sizeof(int), com);
for(int i = 0;i<N;i++){
X[i] -=i;
}
qsort(X, N, sizeof(int), com);
int sum  = 0;
for(int i = 0; i<N;i++){//移动的最⼩步数
sum +=abs(X[i]-X[N/2])+abs(Y[i]-Y[N/2]);
}
cout<<endl;
return 0;
}
关于⽤上⾯所讨论的寻中位数的⽅法可以⾃⼰试试；