今天获取一个任务是限制网教上用户的算法使用方法，详细的题目是输油管道问题，下面是题目。
输水管道问题 某公司计划建造一条由东向西的主输水管道。该管道要穿过一个有n口水井的区域。从每口水井都要有一条输水管道沿最短路经(或南或北)与主管道相连。如果给定n口水井的位置，即它们的x坐标（东西向）和y坐标（南北向），应如何确定主管道的最优位置，即使各水井到主管道之间的输水管道长度总和最小的位置。 注意：要求在线性时间内确定主管道的最优位置。 1<= 水井数量 <=1 000 000 输入要求： 输入有水井数量行，第 K 行为第 K 水井的坐标 X ,Y 。其中， 0<=X<2^31,0<=Y<2^31 。 输出要求： 输出有一行， N 为主管道最优位置的最小值。 例如： 输入： 1,1 2,2 3,3 输出：这道题目总结来说就是查找中位数，详细的解释有很多博文已经阐述得很详细了，在此就不再赘述。普遍使用的方法有两种，一种是简单的排序，另一种是分治法，在这两种方法都可以轻松过掉这道题目的情况下，我打算找方法将快排的方法查掉，只留下分治法。
本题目用例中限制的时间是1s，内存是64M，对于内存我没有太多研究，所以打算从简单的算法耗时上入手，快排的时间是O（nlogn）,分治法的时间是O（logn），对于快排来说最差情况是数据的形式为：mid:=random(r-l)+l，l指左侧即left，r指右侧即right，mid指中间位置，此时的时间是O（n^2），但是对于大多数coder来讲直接使用qsort或者sort是最简单的方法， 然而这两种方法会对数据的情况做出适当的调整，使得时间基本保持在O（nlogn），这就使得我无法从数据的组合上解决这个问题，然后只能大量堆数据，经过测试，数据量达到 “三百万” 的时候，qsort的时间已经慢到了一秒之外，分治法还是在一秒之内的，于是我打算尝试用五百万的数据做隐藏用例，查掉使用简易方法的代码。
下面上一下两种代码。
qsort：
#include<stdio.h> #include<math.h> #include<stdlib.h> int y[1000000]; int comp(const void *a,const void *b) { return *(int*)a-*(int*)b; } void main() { int n=0;//油井数 int a;//油井Y坐标 int i; while(scanf("%d,%d",&a,&y[n])!=EOF) { n++; } qsort(y,n,sizeof(y[0]),comp); if(n%2==0) PRintf("%d/n",y[n/2-1]); else printf("%d/n",y[n/2]); }分治法：
#include<stdio.h> #include<stdlib.h> #include<time.h> #define random(x) (rand()%x) #define MAX 2000010 int main() { int a[MAX],n=0,*up,*eq,*dn,nu=0,ne=0,nd=0,k,x,*p,temp; 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]);return0;} else{p=up;n=nu;k=k-nd-ne;} } return 0; }当然我也不想查掉这些代码，但是毕竟是工作，我也不想这么狠心………..
如果看到这篇博文估计八成是因为被查了吧，要是碰巧是某个学校的学生的话，说不准是我查的，所以这篇博文也写给你们算是补偿吧，好好学习这个方法不要辜负老师的一片苦心……..
新闻热点
疑难解答
