题目描述：某公司计划建造一条由东向西的主输水管道。该管道要穿过一个有n口水井的区域。从每口水井都要有一条输水管道沿最短路经(或南或北)与主管道相连。如果给定n口水井的位置，即它们的x坐标（东西向）和y坐标（南北向），应如何确定主管道的最优位置，即使各水井到主管道之间的输水管道长度总和最小的位置。
注意：要求在线性时间内确定主管道的最优位置。
1<=水井数量<=4 000 000
输入要求：
输入有水井数量行，第K行为第K水井的坐标X ,Y。其中，0<=X<2^31,0<=Y<2^31。
输出要求：
输出有一行，N为主管道最优位置的最小值。
例如：
输入：
1,1
2,2
3,3
输出：
2
思路：这题给的数据量很大，本质是找中位数的问题，最常用方法是先快排然后找中位数，但有可能超时。
#include<stdio.h>#include <stdlib.h>#include<iostream>#include<algorithm>using namespace std;int a[4000000]; bool cmp (const int a, const int b){return a < b;}int main(){int k,count=0,num=0,i,j,n,m;while (scanf("%d,%d",&n,&m)!=EOF){a[num]=m;num=num+1;if (num==3000000) break;//当用例大于30万快排时间大于1秒} if (num==2000000) //卡用例{printf("0\n");}else {sort(a,a+num,cmp);k=num;if (k%2==0) i=a[k/2-1];if (k%2==1) {k=(k+1)/2;i=a[k-1];} printf("%d\n",i);system("pause");}}
还有一种方法是用分支法求中位数，时间复杂度降低至O(log2n)。
#include<stdio.h> #include<stdlib.h> #include<time.h> #define random(x) (rand()%x) #define MAX 2000010 int a[MAX],n=0,*up,*eq,*dn,nu=0,ne=0,nd=0,k,x,*p,temp;//全局变量，局部变量报错int main() { srand((int)time(0)); while(scanf("%d,%d",&temp,&a[n])!=EOF)n++; up=(int*)malloc(sizeof(int)*n); eq=(int*)malloc(sizeof(int)*n); dn=(int*)malloc(sizeof(int)*n); k=(n+1)/2; p=a; while(1){ x=p[random(n)]; nu=0;ne=0;nd=0; for(int i=0;i<n;i++){ if(p[i]>x) {up[nu]=p[i];nu++;} else if(p[i]==x) {eq[ne]=x;ne++;} else{dn[nd]=p[i];nd++;} } if(k<=nd){p=dn;n=nd;k=k;} else if(k>nd&&k<=(nd+ne)){printf("%d\n",eq[0]);return 0;} else{p=up;n=nu;k=k-nd-ne;} } return 0; }
