CS Academy-Manhattan Distances

---

[题目链接]

大意：
二维平面给n个点，在x轴上找一个点使它到离它最近的k个点的曼哈顿距离之和最小

个人题解：
先看问题的简化版,在一维平面（比如x轴）上给$n$个点，找一个点使它到所有点的距离之和最小，设满足条件的点为$p$易证

$$\begin{cases}\text{$p$位于最中间两个数之间}, & \text{if $n$ is even} \\ \text{$p$为最中间那个点},& \text{if $n$ is odd} \end{cases}$$

考虑二维情况下，如果我们选定的点为$x_0$,记离它最近的k个点构成的集合为$S$,则$x_0$到$S$集合中所有点的曼哈顿距离之和为

$$\sum_{i==1}^{k}|x_0-P_{ix}|+P_{iy}\quad P_i\in S$$
即 $$\sum_{i==1}^{k}(x_0-P_{ix}+P_{iy})[x_0>P_ix]+ (P_{ix}-x_0+P_{iy})[x_0<=P_ix]\quad P_i\in S$$
然后大胆猜结论(此题解请勿扩散！！！！)

在二维情况下在x轴上选点和一维同理，最小值一定在某个$x_0$满足有$k/2$个点$P_{ix}<x_0$且有$k-k/2$个点满足$P_{ix}>=x_0$，易得$x_0\in P_{ix}$,然后对每个$x\in P_{ix}$求出它左边有$k/2$个点和右边有$k-k/2$个点的情况加一下取个$min$

$$ans=min((\sum_{i==1}^{k/2}(P_{iy}-P_{ix})[x_0>P_ix]+k*x_0)+(\sum_{i=k/2+1}^{k}(P_{ix}+P_{iy})[x_0<=P_ix]-(k-k/2)*x_0))$$
$$P_i\in S,x_0\in P_{ix}$$

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
#define ull unsigned long long
#define EPS 1e-8
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
const double pi = acos(-1.0);
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return f*x;
}
void write(ll a){
    if (a<0) putchar('-'),a=-a;
    if (a>=10) write(a/10); putchar(a%10+'0');
}
const ll INF=1e18; 
void solve(vector<pll>& p,vector<ll> &ans,ll num,bool flag){
    priority_queue<ll> pq;
    ll sum=0;
    for(auto& ite:p){
        ll x=ite.first,y=ite.second;
        if(flag){
            if((int)pq.size()==num){
                ans.push_back(num*x+sum);
            }else{
                ans.push_back(INF);
            }
        }
        sum+=y-x;
        pq.push(y-x);
        while((int)pq.size()>num){
            sum-=pq.top();
            pq.pop();
        }
        if(!flag){
            if((int)pq.size()==num){
                ans.push_back(num*x+sum);
            }else{
                ans.push_back(INF);
            }
        }
    }
}
int main()
{
    #ifdef TEST
        freopen("input.txt","r",stdin);
    #endif
    ll n,k;
    cin>>n>>k;
    vector<pll> points(n);
    for(auto&ite :points){
        cin>>ite.first>>ite.second;
    }
    sort(points.begin(),points.end());
    vector<ll> left,right;
    solve(points,left,k>>1,true);
    reverse(points.begin(),points.end());
    for(auto &ite:points){
        ite.first*=-1;
    }
    solve(points,right,k-(k>>1),false);
    reverse(right.begin(),right.end());
    ll ans=INF;
    for(int i=0;i<n;i++){
        ans=min(ans,left[i]+right[i]);
    }
    cout<<(ans==INF?points[0].second:ans)<<endl;
    return 0;
}