问题描述: 某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置,即它们的x 坐标(东西向)和y 坐标(南北向),应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的位置? 编程任务: 给定n 口油井的位置,编程计算各油井到主管道之间的输油管道最小长度总和。
如果只有一口井,那么显然是越近越好啦 如果有两口井,那么显然是有以下三种情况: 1.两口井都在主管道北边,那么这个时候的两个连接管道的长度和肯定大于两口井的Y坐标之差 2.两口井都在主管道南边,和情况1是一样的 3.两口井,一个在主管道南边,一个在主管道北边,那么两个连接管道的长度和就等于两口井的Y坐标之差 显然情况三是所要的最短管道的设计情况 就是当主管道在两口井之间的任意位置时,连接管道长度之和都等于两口井的Y坐标之差,是最短的长度 那么将这个结论推广,当有n口井的时候, 1.n是偶数
只要这n口井分布在主管道的两边,一边n/2个,那么就是距离之和最小的 2.n是奇数 只要将这n个井中,Y坐标最中间的(也就是Y是中值的那个)井不算,其余的偶数个井分布在主管道的两侧,这个时候移动主管道,那么这n个连接管道长度之和就决定于那个没有算的井了,因为其余的井的距离之和是固定了的,这个时候只要主管道最接近那个点就好了呀
代码为:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define LEN 100
int Random(int p, int r){//随机化
return rand()*(r-p)/32767+p;
}
void Swap(int &a, int &b){
int temp = a;
a = b;
b = temp;
}
int Partition(int y[LEN], int p, int r){
int i = p, j = r+1;
int x = y[p];
while(true){
while(y[++i]<x&&i<r);
while(y[--j]>x);
if(i>=j) break;
Swap(y[i],y[j]);
}
y[p] = y[j];
y[j] = x;
return j;
}
int RandomizedPartition(int y[LEN], int p, int r){
int i = Random(p,r);
Swap(y[i],y[p]);
return Partition(y,p,r);
}
int RandomizedSelect(int y[LEN], int p, int r, int k){
if(p==r) return y[p];
int i = RandomizedPartition(y,p,r);
int j = i-p+1;
if(k<=j) return RandomizedSelect(y,p,i,k);
else return RandomizedSelect(y,i+1,r,k-j);
}
void main(){
int n;//油井数
int sum = 0;//管道长度总和
int y[LEN];//油井y坐标
int dy;//油井y坐标中位数
scanf("%d",&n);//读取油井数
for(int i=0;i<n;i++){
scanf("%d",&y[i]);//x坐标在此题中无用,而y坐标在x坐标之后写入。因此两次写入一样的数组y[LEN]
scanf("%d",&y[i]);
}
dy = RandomizedSelect(y, 0, n-1, (n+1)/2);//中位数求取
for(i=0; i<n; i++)
sum+=abs(y[i]-dy);//计算管道和
printf("%d\n",sum);
}
分享到:
相关推荐
输油管道问题,在VC6.0中实现,算法参考《计算机算法设计与分析》(王晓东)。分治算法RandomizedSelect
输油管道问题:可能有点小问题,自己修改一下,只提供参考。
输油管道问题,程序设计,程序源码……………… 内含具体设计方法
输油管道问题 Time Limit:2000MS Memory Limit:65536K Total Submit:392 Accepted:242 Description 问题描述: 某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都...
输油管道问题 某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置,即它们的x 坐标(东西向)...
本个资源还可以!可能在某环境下不能运行!总之,还可以的!
某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置,即它们的x 坐标(东西向)和y 坐标(南北...
改进的可以在C语言环境下实现的算法,可能还有许多需要改进的地方。
#include "stdio.h" #include "stdlib.h" #include "math.h" main() {int i,j,sum=0,n,mode=0,temp,z; scanf("%d",&n); int a[n+1]; for(i=1;i;i++) scanf("%d%d",&z,&a[i]); for(i=1;i;... }
某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n 口油井的位置,即它们的x 坐标(东西向)和y 坐标...
讲述经典的输油管道问题,分析的比较具体,很值得一看
输油管道问题排序
输油管道问题(分治)定义.pdf
某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置,即它们的x坐标(东西向)和y坐标(南北向...