某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路径与主管道相连。如果给定n口油井的位置，应如何确定主管道的最优位置，即使各油井到主管道之间的输油管道长度最小长度总和。
#include <iostream>
#include <cmath>
using namespace std;
#define NUM 1001
int a[NUM];
int select(int left, int right, int k)
{
if (left >= right) return a[left];
int i = left;
int j = right + 1;
int pivot = a[left];
while (true)
{
do {
i = i + 1;
} while (a[i] < pivot);
do {
j = j - 1;
} while (a[j] > pivot);
if (i >= j) break;
swap(a[i], a[j]);
}
if (j - left + 1 == k) return pivot;
a[left] = a[j];
a[j] = pivot;
if (j - left + 1 < k)
return select(j + 1, right, k - j + left - 1);
else return select(left, j - 1, k);
}
int main()
{
int n;
int x;
int y;
int k;
cout << "Please enter n !\n";
cin >> n;
cout << "Please enter x and y！\n";
for (int i = 0; i<n; i++)
cin >> x >> a[i];
/*判断k的取值*/
if (n%2==0)
{
k = n / 2;
}
else
{
k = (n + 1) / 2;
}
y = select(0, n - 1, k); //调用分治法找出第k小元素的算法
cout << "纵坐标的中位数为：" << y << endl;
/*计算各个输油管道到主管道最小长度总和*/
int min = 0;
for (int i = 0;i<n;i++)
min += (int)fabs(a[i] - y);
cout << "最小长度为："<<min << endl;
return 0;
}
运行结果
