今天一个朋友问我一到题。其实翻译过来就很简单了。
Professor Olay is consulting for an oil company, which is planning a large pipeline running east to west through an oil field of n wells. The company wants to connect a spur pipeline from each well directly to the main pipeline along a shortest route (either
north or south), as shown in Figure 9.2. Given the x- and y-coordinates of the wells, how should the professor pick the optimal location of the main pipeline, which would be the one that minimizes the total length of the spurs? Show how to determine the optimal
location in linear time.
输油管道问题:某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田，从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置,即它们的x坐标（东西向）和y坐标（南北向）,应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的位置?证明可在线性时间内确定主管道的最优位置。
#include<stdio.h>
#include<conio.h>
#include<math.h>
#define N 20
int main()
{
void path(int [],int);
int array[N];
int i,n;
printf("请输入油井的个数:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("请输入第%d个管道的纵坐标:",i+1);
scanf("%d",&array[i]);
}
path(array,n);
getch();
}
void path(int a[],int n)
{
int i,j,temp,minimum=0,minimum2=0;
for(i=1;i<=n-1;i++)
for(j=0;j<=n-2;j++)
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
printf("\n管道位置纵坐标为y=%d",a[n/2]);
for(i=0;i<n;i++)
minimum+=(int)fabs(a[i]-a[n/2]);
printf("\n最优管道长度为:%d",minimum);
}
这个代码虽然实现了，但是时间复杂度很大。不得不重新考虑，在网上找了类似题目的代码进行更改
#include <fstream.h>
#include <math.h>
int part(int* a,int start,int end)
{
int i,j,x,temp;
i=start;
j=end+1;
x=a[start];
while(1)
{
while(i<end&&a[++i]<x);
while(j>start&&a[--j]>=x);
if(i>=j)
break;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
a[start]=a[j];
a[j]=x;
return j;
}
int selectK(int* a,int start,int end,int k)
{
int partPos,position;
if(start==end)
return a[start];
partPos=part(a,start,end);
position=partPos-start+1;
if(k<=position)
return selectK(a,start,partPos,k);
else
return selectK(a,partPos+1,end,k-position);
}
void main()
{
int i,n,sum,middle;
int* a;
fstream file;
file.open("input.txt",ios::in);
file>>n;
a=new int[n];
for(i=0;i<n;i++)
file>>a[i]>>a[i];
file.close();
middle=selectK(a,0,n-1,(n+1)/2);
for(i=0,sum=0;i<n;i++)
sum+=abs(a[i]-middle);
file.open("output.txt",ios::out);
file<<sum;
file.close();
delete []a;
a=0;
}
在网上还看到了类似的问题：
邮局选址问题:在一个按照东西和南北方向划分成规整街区的城市里，n个居民点散乱地分布在不同的街区中，用x来表示东西向，用y坐标来表示南北向，各居民点的位置可以有坐标(x,y)来表示，街区中任意两点(x1,y1),(x2,y2)之间的距离可以用数值|x2-x1|+|y2-y1|来度量。居民们希望在城市中选择建立邮局的最佳位置，使n个居民点到邮局的距离总和最小。试设计一个算法，求出邮局的最佳位置和居民点到邮局的最短距离。
#include<stdio.h>
#include<conio.h>
#include<math.h>
#define N 10
struct location
{
int x;
int y;
};int main()
{
void path(struct location [],int);
struct location array[N];
int i,n;
printf("请输入居民点的个数:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("请输入第%d个居民位置:",i+1);
scanf("%d,%d",&array[i].x,&array[i].y);
}
path(array,n);
getch();
}
void path(struct location a[],int n)
{
int i,j,b1,b2,c1,c2,temp1,temp2,minimum=0;
for(i=1;i<=n-1;i++) /*给位置排序，以便搜索中位值*/
for(j=0;j<=n-2;j++)
{
b1=(int)fabs(a[j].x)+(int)fabs(a[j].y);
b2=(int)fabs(a[j+1].x)+(int)fabs(a[j+1].y);
if(b1>b2) /*第一个点的x+y比第二个点的小*/
{
temp1=a[j].x;
a[j].x=a[j+1].x;
a[j+1].x=temp1;
temp2=a[j].y;
a[j].y=a[j+1].y;
a[j+1].y=temp2;
}
if(b1==b2) /*当x+y相等的情况下，计算点的x*x+y*y是否相等*/
{
c1=a[j].x* a[j].x+a[j].y*a[j].y;
c2=a[j+1].x* a[j+1].x+a[j+1].y*a[j+1].y;
if(c1<c2)
{
temp1=a[j].x;
a[j].x=a[j+1].x;
a[j+1].x=temp1;
temp2=a[j].y;
a[j].y=a[j+1].y;
a[j+1].y=temp2;
}
}
}
printf("\n邮局的最优位置为x=%d,y=%d",a[n/2].x,a[n/2].y);
for(i=0;i<n;i++)
minimum+=(int)fabs(a[i].x-a[n/2].x)+(int)fabs(a[i].y-a[n/2].y);
printf("\n居民点到邮局最短距离之和为:%d",minimum);
}
分享给大家、