题解 | # P1862 输油管道问题 #

$[中位数定理]$

求 $\sum_{i=1}^{n}{\left| x_{i}-x \right|}$ 的最小值，当 $x$ 等于 $x_{1},x_{2},...,x_{n}$ 的中位数时， $\sum_{i=1}^{n}{\left| x_{i}-x \right|}$ 取得最小值。即将 $x_{1},x_{2},...,x_{n}$ 升序排列后， $x=x_{\frac{n+1}{2}}$

题目一：https://www.luogu.com.cn/problem/P1862

显然只与总坐标有关，即求 $\sum_{i=1}^{n}{\left| y_{i}-x \right|}$ ，将 $y$ 升序排列后，当 $x=y_{\frac{n+1}{2}}$ 时值最小

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;

void solve(){
    
    int n; cin >> n;
    vector<int> a(n + 10);
    for(int i = 1; i <= n; i ++){
        cin >> a[i] >> a[i];
    }
    sort(a.begin() + 1, a.begin() + 1 + n);
    int ans = 0;
    for(int i = 1; i <= n; i ++){
        ans += abs(a[i] - a[(n + 1) / 2]);
    }
    cout << ans << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    while(tt --) solve();
    return 0;
}

题目二：https://www.luogu.com.cn/problem/P1632
由中位数定理可知如果将所有点移动到某点 $(x,y)$ 满足最小距离，则 $x=x_{i},y=y_{j}$ ，其中 $1\leq i,j\leq n$ ，意思是 $x,y$ 一定是某一点的横左边以及某一点的纵左边，不一定是同一点，那么我就可以全部枚举横纵坐标：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;

const int inf = 1000000000000000000;
void solve(){
    int n; cin >> n;
    vector<int> x(n + 10), y(n + 10);
    for(int i = 1; i <= n; i ++) cin >> x[i] >> y[i];
    vector<int> pre(n + 10, inf); 
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= n; j ++){
            vector<int> dis;
            for(int k = 1; k <= n; k ++) dis.push_back(abs(x[k] - x[i]) + abs(y[k] - y[j]));
            sort(dis.begin(), dis.end());
            for(int i = 1; i < n; i ++) dis[i] += dis[i - 1];
            for(int i = 0; i < n; i ++) pre[i] = min(pre[i], dis[i]);
        }
    }
    for(int i = 0; i < n; i ++) cout << pre[i] << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    while(tt --) solve();
    return 0;
}

题目三：https://www.luogu.com.cn/problem/P1889

观察纵坐标，因为最终纵坐标一样，所以就是普通的中位数定理，即求 $\sum_{i=1}^{n}{\left| y_{i}-x \right|}$
再看横坐标，求 $\sum_{i=1}^{n}{\left| x_{i} - (x+i-1) \right|}$ 的最小值，即求 $\sum_{i=1}^{n}{\left| (x_{i} - i+1)-x \right|}$ 的最小值，这也可以使用中位数定理，令 $z_{i} = x_{i}-i+1$ ，那么求 $\sum_{i=1}^{n}{\left| z_{i}-x \right|}$ ，首先对 $x_{i}$ 从升序排序，然后依次减去 $(i-1)$ ，满足“小减去小，大减去大”，这样使得整个序列趋向均匀，最后用中位数定理即可

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;

void solve(){
    
    int n; cin >> n;
    vector<int> x(n + 10), y(n + 10);
    for(int i = 1; i <= n; i ++) cin >> x[i] >> y[i];
    sort(x.begin() + 1, x.begin() + 1 + n);
    sort(y.begin() + 1, y.begin() + 1 + n);
    int ans = 0;
    for(int i = 1; i <= n; i ++){
        x[i] -= (i - 1);
        ans += abs(y[(n + 1) / 2] - y[i]);
    }
    sort(x.begin() + 1, x.begin() + 1 + n);
    for(int i = 1; i <= n; i ++) ans += abs(x[(n + 1) / 2] - x[i]);
    cout << ans << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    while(tt --) solve();
    return 0;
}