题目
主油管道为东西向,确定主油管道的南北位置,使南北向油井喷油管道和最小。要求线性时间完成。
1<= 油井数量 <=2 000 000
输入要求:
输入有油井数量行,第 K 行为第 K 油井的坐标 X ,Y 。其中, 0<=X<231,0<=Y<231 。
输出要求:
输出有一行, N 为主管道最优位置的最小值
分析:
管道为东西向,则求所有油井南北方向到管道最小距离和。这题虽然给了两个坐标,其实只和油井坐标的Y坐标有关系,就是求所有Y坐标的中位数,中位数对应位置,所有油井到管道距离和最小。
不能用排序。(排序还用你写?)
我们采用分治,能达到Logn的时间复杂度。
采用最坏时间O(n)线性选择算法。见下代码
#include<bits/stdc++.h>
using namespace std;
int oil[2000005];
int insertSort(int x) {//找五个数中位数
for(int i = 0; i < 3; i++) {
for(int j = i + 1; j < 5; j++) {
if(oil[x + j] > oil[x + i]) {
swap(oil[x + j], oil[x + i]);
}
}
}
return 0;
}
int Partition(int l, int r, int p) {//将all[l.r]以p为基准分开
int i, j;
for(i = l; i <= r; i++) //目的以all[p]为基准划分
{
if(p == oil[i]) {
swap(oil[i], oil[l]);
break;
}
}
i = l, j = r + 1; //左右同时遍历到第一个符合条件,交换值(类似快速排序思想)
while (1){
while (oil[++i] < p && i < r);
while (oil[--j] > p);
if (i >= j)
break;
swap(oil[i],oil[j]);
}
oil[l] = oil[j];
oil[j] = p;
return j;
}
int select(int l, int r, int k)
{
if(r - l < 75)//小于七十五用普通排序更方便
{
sort(oil + l, oil + r + 1);
return oil[l + k - 1];
}
for(int i = 0; i <= (r - l - 4) / 5; i++) {
insertSort(l + 5*i);
swap(oil[l + i], oil[l + 5*i + 2]);
}
int mid = select(l, l + (r - l - 4) / 5, (r - l - 4) / 10);
int i = Partition(l, r, mid);
int len = i - l + 1;
if(len == k) {
return oil[i];
}
else if(k < len) {
return select(l, i - 1, k);
}
else {
return select(i + 1, r, k - len);
}
}
int main() {
int a, b, n = 0;
while(scanf("%d,%d", &a, &b) != EOF) {
oil[n++] = b;
}
if(n % 2 == 1) {
cout << select(0, n - 1, (n + 1) / 2) << endl;
}
else {
cout << select(0, n - 1, n / 2) << endl;
}
return 0;
}