Description

某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有$n$口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定$n$口油井的位置,即它们的$x$坐标（东西向）和$y$坐标（南北向）,应如何确定主管道的最优位置, 即使各油井到主管道之间的输油管道长度总和最小的位置?证明可在线性时间内确定主管道的最优位置。给定$n$口油井的位置,计算各油井到主管道之间的输油管道最小长度总和。

Input

输入数据的第$1$行是油井数$n$，$1≤n≤10000$。接下来$n$行是油井的位置，每行$2$个整数$x$和$y$，$-10000≤x,y≤10000$。

Output

输出一个整数，表示油井到主管道之间的输油管道最小长度总和。

Sample Input

5
1 2
2 2
1 3
3 -2
3 3

Sample Output

6

问题分析

中位数定理:
$\color{Blue}{如果有一个数轴,数轴上有若干个点.要在数轴上找一点,使得它到各个点的距离之和最短,中位数就是最优解.}$
所有数与中位数的绝对差之和最小,中位数是数列中间的那个数,或者是中间的那两个数之一.

已知: $\left| x-a\right|+\left| x-b\right| \geqslant \left| a-b\right|$

故$\left| x-a_1\right|+\left| x-a_2\right|+…+\left| x-a_{n-1}\right|+\left| x-a_n\right|$
$=(\left| x-a_1\right|+\left| x-a_n\right|)+(\left| x-a_2\right|+\left| x-a_{n-1}\right|)+…$
$\geqslant \left| a_1-a_n \right|+\left| a_2-a_{n-1}\right|+…$
同时取等号时最小,要求$x$在$a_1$和$a_n$之间,在$a_2$和$a_{n-1}$之间,…
即当x为中位数时取得最小值$min\sum_{k=1}^{n}\left| x-a_i\right|$

故只需要找到中位数即可,当$n$为奇数时(下标从$1$开始),中位数是$a_{\frac{n+1}{2}}$;当$n$是偶数时,中位数左边是$a_{\frac{n}{2}}$(亦可写成$a_{\frac{n+1}{2}}$,为了与奇数情况一致),中位数右边是$a_{\frac{n}{2}+1}$,偶数的时候选择左边右边都可以,故综上中位数取为$a_{\frac{n+1}{2}}$.

官方题解

代码实现

第一种方式采用对坐标$(x,y)$的$y$进行排序,选择其中位数作为其最优值

/**
  * @author  : SDTBU_LY
  * @version : V1.0.0
  * @上联    : ac自动机fail树上dfs序建可持久化线段树
  * @下联    : 后缀自动机的next指针DAG图上求SG函数
**/

#include<iostream>
#include<cstring>
#include<algorithm>

#define MAXN 10010

using namespace std;

typedef long long ll;

int n,y[MAXN];

int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0),cout.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin >> x >> y[i];
    }
    sort(y+1,y+n+1);
    int res=0;
    for(int i=1;i<=n;i++)
        res+=abs(y[i]-y[(n+1)/2]);
    cout << res << endl;
    return 0;
}

第二种方式采用快速选择($quick$_$select$)实现查找中位数——分治思想

/**
  * @author  : SDTBU_LY
  * @version : V1.0.0
  * @上联    : ac自动机fail树上dfs序建可持久化线段树
  * @下联    : 后缀自动机的next指针DAG图上求SG函数
**/

#include<iostream>
#include<cstring>
#include<algorithm>

#define MAXN 10010

using namespace std;

typedef long long ll;

int n,y[MAXN];

int quick_select(int l,int r,int k)
{
    if(l==r)
        return y[l];
    int temp=y[(l+r)/2],i=l-1,j=r+1;
    while(i<j)
    {
        do i++;
        while(y[i]<temp);
        do j--;
        while(y[j]>temp);
        if(i<j)
            swap(y[i],y[j]);
    }
    int s1=j-l+1;
    if(k<=s1)
        return quick_select(l,j,k);
    else return quick_select(j+1,r,k-s1);

}


int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0),cout.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin >> x >> y[i];
    }
    int num=quick_select(1,n,(n+1)/2);
    int res=0;
    for(int i=1;i<=n;i++)
        res+=abs(num-y[i]);
    cout << res << endl;
    return 0;
}