题解：P13080 [NOISG 2017] Best Places / 最佳选址

· · 题解

显然曼哈顿距离之和的 x 和 y 是割裂的，可以分开考虑。

于是问题转化成给你一堆数，让你找一个数使得 \sum |a[i]-x| 最小。

我们注意到，如果只有两个数，那么 x 取两数之间即可；如果有三个数，那么 x 取第二大的数即可；如果有四个数，那么 x 取第二、第三大的数之间即可。

由此注意到，若总数是奇数，必然取在中位数，反之，取中间两数之间，当然，可以取中间两数中的任何一个数。

于是取第 \lfloor \frac{n-1}{2} \rfloor+1 个数即可。

#include<bits/stdc++.h>
using namespace std;
int n , x[1000010] , y[1000010]; 
int main()
{
    scanf("%d" , &n);
    for(int i = 1 ; i <= n ; i ++) scanf("%d%d" , &x[i] , &y[i]);
    sort(x + 1 , x + n + 1) , sort(y + 1 , y + n + 1);
    printf("%d %d" , x[(n - 1) / 2 + 1] , y[(n - 1) / 2 + 1]);
    return 0;
}