codeforces Educational Codeforces Round 16 B. Optimal Point on a Line

問題

問題概要

x座標上のnこの点が与えられる。それらの点の中から、他の点までの距離の合計が最小となるものを見つけろ。

解法

中央値は母集団の各要素から絶対距離の和が最も小さくするという意味で母集団を代表していると見ることができる(Wikipedia)とかいてあった。つまり、今回の問題で求めたい答えは中央値ということ。答えが複数ある時は、最も小さいものを選ぶので、nが偶数の時は左のものを選んでいる。

ミス

中央値なるほどね、て感じ。中央値を求める時に、真ん中２つで平均をとる意味あるの?

コード

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

int main(void){
    int n; cin >> n;
    vector<int> v(n);
    rep(i, n) cin >> v[i];
    sort(v.begin(), v.end());
    //中央値を計算
    if(v.size() % 2 == 0){
        printf("%d\n", v[v.size() / 2 - 1]);
    }else{
        printf("%d\n", v[v.size() / 2]);
    }
    return 0;
}