SRM324 D1M TournamentPlan - ry0u

TopCoder Statistics - Problem Statement
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

$(street[i], avenue[i])$に$i$番目の人がいて，どこかの地点に集まりたい．集まる地点からのマンハッタン距離の合計を最小化したい．

これがマンハッタン距離でなくてユークリッド距離であれば，全て足してその平均を取れば良い(重心)．実際に重心からそんなに離れないだろうと思って重心を中心に$-1000, 1000$ぐらいずらして見たけどサンプルが合わない．

思考が止まってしまって，探索するのかと考えたけど全然分からない．解説を見るとマンハッタン距離なので，これが平均でなくて中央値で良いらしい．感覚は分かるけど，証明があまり良くわかっていない．

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <cmath>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

class TournamentPlan {

    public:

    int getTravelDistance(vector <int> street, vector <int> avenue) {
      int n = street.size();

      sort(street.begin(), street.end());
      sort(avenue.begin(), avenue.end());

      int x = street[n / 2];
      int y = avenue[n / 2];

      int ans = 0;
      rep(i, n) {
          ans += abs(street[i] - x) + abs(avenue[i] - y);
      }

      return ans;
    }
};