Problem Description

image.png

主油管道为东西向，确定主油管道的南北位置，使南北向油井喷油管道和最小。要求线性时间完成。

1<= 油井数量 <=2 000 000

输入要求：

输入有油井数量行，第 K 行为第 K 油井的坐标 X ,Y 。其中， 0<=X<2^31,0<=Y<231 。

输出要求：

输出有一行， N 为主管道最优位置的最小值

注意：用快排做的不给分！！

友情提示：可以采用while(scanf("%d,%d",&x,&y) != EOF)的数据读入方式。

测试输入

41,969978
26500,413356
11478,550396
24464,567225
23281,613747
491,766290
4827,77476
14604,597006
292,706822
18716,289610
5447,914746

测试输出

597006

Ac code

#include <iostream>
#include <stdio.h>
#include <stdlib.h>

int arr[2000000];
int RandomizedSelect(int arr[],int p,int r,int k);

int Partition(int arr[],int p,int r){

    int i= p,j = r + 1;
    int x = arr[p];
    while (1){

        while(arr[++i] < x && i < r);
        while(arr[--j] > x);
        if(i >= j)break;
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;

    }
    arr[p] = arr[j];
    arr[j] = x;
    return  j;

}
int RandomizedPartition(int arr[],int p,int r){
    int i = (rand() % (r-p+1))+ p;
    int temp = arr[i];
    arr[i] = arr[p];
    arr[p] = temp;
    return Partition(arr,p,r);
}
int RandomizedSelect(int arr[],int p,int r,int k){

    if(p == r){
        return arr[p];
    }
    int i = RandomizedPartition(arr,p,r),j = i - p + 1;

    if(k <= j){
        return RandomizedSelect(arr,p,i,k);
    }

    else return  RandomizedSelect(arr,i + 1,r,k - j);
}



int main() {

    int x,y,n;
    n=0;

    while(scanf("%d,%d",&x,&y) != EOF){
        
        arr[n++] = y;
    }

    int mid;
    if(n%2==0)mid = n/2;
    else mid = (n+1)/2;

    printf("%d\n",RandomizedSelect(arr, 0 , n-1 , mid));


    return 0;
}