题目要求:某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路经（或南或北）与主管道相连。
如果给定n口油井的位置，即它们的x坐标（东西向）和y坐标（南北向），应如何确定主管道的最优位置，即使各油井到主管道之间的输油管道长度总和最小的位置？
算法设计的思想:
1.问题实际上可以转化成一维问题,即油井到管道的距离只喝纵坐标有关,故可以将对象抽象到一条y方向的数轴上面。
2.已知，如果是两个井，则管道穿过二者中间；如果是三个井，则管道穿过最中间的一个点。归纳一下即为，管道的纵坐标应该是所有油井的纵坐标的中位数。
问题转化为求，n个数的中位数.。
求中位数的分治思想：
1.如果这组数是有序的，那么这个数组的中位数就是a[n/2];直接用排序中用到分治法的冒泡排序进行排序,但是这样一方面时间复杂度nlogn较高,一方面我们并不想排序,多做了无用的步骤,算法效率不高.
2.线性时间复杂度下的选择算法。实际上还是利用快速排序，进行选择。代码如下.
#include<stdlib.h>//绝对值函数
#include<stdio.h>
#define N 10000
void Swap(int &a,int &b)
{
int t=a;
a=b;
b=t;
}
int Partion (int a[],int l,int h)//a数组,l表示下限,h表示上限
{
int x=a[l];
//将小于x的元素交换到左边区域,将大于x的元素交换的右边区域
while(l<h)
{
while(l<h&&a[h]>=x) --h;
Swap(a[l],a[h]);
while(l<h&&a[l]<=x) ++l;
Swap(a[l],a[h]);
}
a[l]=x;
return l;//返回数轴的位置
}
int Select(int a[],int l,int h,int k)
{
if(l==h) return a[l];
int i=Partion(a,l,h);
int j=i-l+1; //表示这个数轴是整个数组中第几小的.
if(k<=j)//如果比第k小的数要大,则在比它小的数中中在找第k小的
return Select(a,l,i,k);
else//如果比第k小的数要大,则只需要在比它大的数中找,第k-j大的
return Select(a,i+1,h,k-j);
}
int main()
{
int a[N],b[N];
int n,mid,sum=0;
scanf("%d",&n);
for(int i=0; i<n; i++)
scanf("%d %d",&b[i],&a[i]);
mid=Select(a,0,n-1,n/2+1);
printf("mid=%d\n",mid);
for(int i=0; i<n; i++)
sum+=abs(a[i]-mid);
printf("%d",sum);
return 0;
}
输入输出样例
5
1 2
2 2
1 3
3 -2
3 3
输出
mid=2
6
时间复杂度分析
平均时间复杂度为O(n)
