油井问题

成绩: 5 / 折扣: 0.8

题目见教材P41.2-1

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

输入要求：

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

输出要求：

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

 

 

解：

 

其实就是求中位数，X坐标是不要用的，算法书上到处都有，直接贴代码：

#include 
    
     #include 
     
      #define MAX 2000002long a[MAX];int partition(long p,long r){	long i = p, j = r + 1, x = a[p], temp;	while (1)	{		while (a[++i] < x && i < r);		while (a[--j] > x);		if (i >= j) break;		temp = a[i];		a[i] = a[j];		a[j] = temp;	}	a[p] = a[j];	a[j] = x;	return j;}long random(long p,long r){	long temp, i = (rand() % (r + 1 - p)) + p;	temp = a[i];	a[i] = a[p];      	a[p] = temp;	return partition(p, r);}long select(long p, long r,long k){	long i, j;	if(p == r) return a[p];	i = random(p,r);	j = i - p + 1;    	if(k <= j) return select(p,i,k);		else return select(i + 1,r,k - j);} int main(){	long num = 0,temp;	while(scanf("%ld,%ld",&temp,&a[num] )!=EOF) num = num + 1;	if(num%2 == 0) temp = num/2+1;		else temp = num/2+2;	printf("%d\n",select(0,num,temp));	system("pause");	return 0;}