某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有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;
}

运行结果