某石油公司計(jì)劃建造一條由東向西的主輸油管道习柠。該管道要穿過一個(gè)有n口油井的油田芳来。從每口油井都要有一條輸油管道沿最短路徑與主管道相連梆暮。如果給定n口油井的位置捉超，應(yīng)如何確定主管道的最優(yōu)位置胧卤，即使各油井到主管道之間的輸油管道長(zhǎng)度最小長(zhǎng)度總和。
#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); //調(diào)用分治法找出第k小元素的算法
cout << "縱坐標(biāo)的中位數(shù)為：" << y << endl;
/*計(jì)算各個(gè)輸油管道到主管道最小長(zhǎng)度總和*/
int min = 0;
for (int i = 0;i<n;i++)
min += (int)fabs(a[i] - y);
cout << "最小長(zhǎng)度為："<<min << endl;
return 0;
}
運(yùn)行結(jié)果
