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

思路：

对于一维数轴上的坐标，使所有点到该点的距离之和最小的点是该点集的中位数。因此，最优

X

坐标是所有选手

X_i

的中位数，最优

Y

坐标是所有选手

Y_i

的中位数。

求中位数时，排序，再取中间数即可。

AC Code:

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int x[N],y[N],n;
int main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
    }
    sort(x+1,x+1+n);//排序求中位数
    sort(y+1,y+1+n);
    cout<<x[n/2+1]<<" "<<y[n/2+1];//下标从一开始，所以要+1
    return 0;
}

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

文章操作

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

思路：

AC Code:

相关推荐

评论

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