输水管道问题

问题描述

某公司计划建造一条由东向西的主输水管道。该管道要穿过一个有n口水井的区域。从每口水井都要有一条输水管道沿最短路经(或南或北)与主管道相连。如果给定n口水井的位置，即它们的x坐标（东西向）和y坐标（南北向），应如何确定主管道的最优位置，即使各水井到主管道之间的输水管道长度总和最小的位置。

注意：要求在线性时间内确定主管道的最优位置。

1<= 水井数量 <=4 000 000

输入要求：输入有水井数量行，第 K 行为第 K 水井的坐标 X ,Y 。其中， 0<=X<2³¹，0<=Y<2³¹。

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

输入样例

1,1 2,2 3,3

输出样例

2

问题分析

首先，问题涉及到如下所述的一个数学性质：

中位数原理： 在x轴上有n个点，由左至右分别为$x_1,x_2,...,x_n$，寻找一个点$x_p$（不一定是n个点之一），使$x_p$到各点距离和最小，解为： $$f(x)=\{\begin{array}{ll}{x}_{\frac{n+1}{2}}& \text{当n为奇数时}\\ 中间两点的闭区间上& \text{当n为偶数时}\end{array}$$

由题意，主管道是东西方向的，要求各水井到主管道之间的输水管道长度总和最小的位置，即是求各水井纵坐标的中位数。 课本《计算机算法设计与分析（第5版）》（王晓东）的“线性时间选择”一节，针对寻找n个元素的第k小元素，给出了两种思路，分别是RandomizedSelect（P27）和Select（P28）。前者的平均时间为O(n)，最坏时间为O(n²)。后者的最坏时间为O(n)，真正达到了线性时间选择的目的。本问题，即是要求“线性时间选择”出中位数。但是第二个算法Select虽然理论上时间复杂度较低，实际编写程序时较为麻烦，其函数之间的调用也很麻烦，不简洁。详情请看课本，因为不是这篇博客的重点，所以就不放代码和原理了。

这里介绍一个比较易于理解的算法，类似于RandomizedSelect，叫做“荷兰国旗算法”。 可以看到，荷兰国旗分为上中下三部分，分别为红色、白色、蓝色。荷兰国旗算法达成的目的是：给定一列数，选择一个基准k，将整个数组重排为三部分：小于k的数，等于k的数，大于k的数，就像荷兰国旗的蓝白红三个区域一样。而小于k的数和大于k的数这两个区域内的数不一定是有序的。

（至于说世界上的条纹国旗那么多，为什么这个算法叫荷兰国旗算法而不叫其他国家的国旗算法，我也不知道hhh）

明白了算法所达成的目的之后，我们只需要随机选择一个基准，然后对油井的纵坐标使用荷兰国旗算法，接着判断中位数位于三个部分的哪一部分，然后继续递归地对那一部分使用荷兰国旗算法即可。具体可以看AC代码。

AC代码

#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; int a[4000005],n; int partition(int l,int r,int k) //荷兰国旗问题，在区间[l,r]上找第k小的元素 { int m=rand()%(r-l+1)+l; //随机选择一个基准 int pos=a[m]; //基准代表的元素 int i=l-1,j=r+1,p=l; //i代表小于基准的部分的右界，j代表大于基准的部分的左界，p为当前讨论的位置 while (p<=j-1) { if (a[p]<pos) //如果当前位置小于基准 { i++; swap (a[p],a[i]); //将当前位置的元素扔到小于基准的部分 p++; } else if (a[p]>pos) //如果当前位置大于基准 { j--; swap (a[p],a[j]); //将当前位置的元素扔到大于基准的部分 } else p++; //如果当前位置等于基准 } if (i-l+1>=k) return partition(l,i,k); //如果中位数在小于基准的部分，就继续在这部分找第k小的元素 else if (j-l>=k) return a[i+1]; //如果在等于基准的部分，说明就是基准，直接返回 else return partition(j,r,k-(j-l)); //如果在大于基准的部分，则在这部分找第k-(j-l)小的元素 } int main() { int x,y; while (scanf ("%d,%d",&x,&y)!=EOF) { a[n]=y; n++; } printf ("%d\n",partition(0,n-1,(n+1)/2)); //在整个数组上找中位数 return 0; }

这个算法思路和编写都比较简洁，也满足在线性时间内确定主管道的最优位置的要求（至少平均时间是线性的，不太会证明），可以通过本题。

p.s. 其实还有更简洁的写法，直接使用algorithm库中的nth_element啊（不是 不过它就是专门用来求第k小元素的函数……在2018年新生赛考过，知道这个函数就能通过，否则就TLE……