实验五 输油管道问题的设计与实现
[实验目的]
1、掌握分治算法的基本原理
2、利用分治策略编程解决输油管道问题
[实验内容]
问题描述
某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n 口油井的位置，即它们的x 坐标（东西向）和y 坐标（南北向），应如何确定主管道的最优位置， 即使各油井到主管道之间的输油管道长度总和最小的位置？
1.请给出分析与解答；
2.给出代码和运行结果；
3.估算算法的时间复杂度。
关于确定主管道的最优位置：由于主管道是由东向西，则主管道的铺设位置只和各油井位置的y坐标有关，要求的最优主管道的位置y坐标应是各个油井y坐标的中位数。
反证法证明之：
油井数目为奇数：假设主管道的最优位置ｙ坐标值为y_ave,不是各个油井位置ｙ坐标的中位数y_mid，我们可以假设y_ave>y_mid，ｙ坐标小于y_ave的油井数目为m,ｙ坐标大于y_ave的油井数目为n，显然有m>n。当我们将主管道位置下移距离x时(假设此时仍满足y_ave>=y_mid)，各油井到主管道之间的输油管道长度总和应增加nx-mx，显然nx-mx<0(m>n)，即存在一个比_ave更优的位置使得各油井到主管道之间的输油管道长度总和更小，这与假设矛盾。当y_ave>y_mid时，同理可证。
油井数目为偶数时：同理可证 。
分析：于是此题就转化为了求中位数，关于求中位数，可以先排序，然后中间那个就是所求，但是为了体现分治的思想，同时追求更高的效率，于是本次用随机选择算法，随机选择算法和快速排序有点像。
随机选择算法求中位数：如果是奇数个点，就是中间那个，如果是偶数个点，下面代码求的是中间靠左的那个数，当然油田放在中间靠右的那个也可以，各油井到主管道之间的输油管道长度总和是一样的，随机选择算法和快排差不多，先让第一个数找到对应的位置，比它小的放左边，比它大的放它右边，然后如果被排序的位置是中位数，则返回之，如果中位数的位置小于这个位置，就对左区域进行随机选择算法，反之则对右区域进行随机选择算法。
源代码：
#include<cstdio>
#include<iostream>
using namespace std;
struct point
{
int x,y;//存储油田坐标信息
} a[1000];
int exquick(point *a,int left,int right,int n)
{
int ll=left,rr=right,y=a[left].y;
while(ll<rr) //这步和快速排序差不多,把比它小的放左边，比它大的放右边
{
while(ll<rr&&a[rr].y>=y) rr--;
a[ll]=a[rr];
while(ll<rr&&a[ll].y<=y) ll++;
a[rr]=a[ll];
}
if(ll==(n-1)/2) return y;//如果是中位数，则返回之
if(ll>(n-1)/2) return exquick(a,left,ll-1,n);//如果中位数在它的左边，则在左区域寻找
return exquick(a,ll+1,right,n); //反之，在右区域寻找
}
int main()
{
int n,t,ans;//n为油田个数
cout<<"请输入油田个数：";
cin>>n;
for(int i=0; i<n; i++)
{
cout<<"请输入油田坐标：";
cin>>a[i].x>>a[i].y;
}
cout<<"最优位置为：y="<<exquick(a,0,n-1,n)<<endl;
return 0;
}
测试数据1：
5
1 2
2 2
1 3
3 -2
3 3
运行结果截图：
测试数据2：
6 1 6 2 -2 1 3 3 -2 3 3 1 1
运行结果截图：
时杂度分析：该算法的时间复杂度为O(n).
