SRM423 Div.1 Easy

問題

無限に広がるマス上にn個のチェッカーがあり、そのうちi個(1 <= i <= n)のチェッカーを同じマスに移動するまでの移動数の合計の最小を求める。

方針

解となるx,y座標は入力として与えられるx,y座標の中にあるはずなので、それぞれ50*50=2500通りの
解が考えられる。
これらの候補に対し入力されたすべてのチェッカーからの移動距離(マンハッタン距離)を調べてソートした上で小さいものからi個の和の最小値を入れていけばよい。

計算量はO(50^4)ぐらい。充分間に合う。

以下ソースコード

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

#define dump(x)  cerr << #x << " = " << (x) << endl;
inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}

class TheTower {
     public:

     vector <int> count(vector <int> x, vector <int> y) {
       vector<int> ret;
       int n=x.size();
       set<int> xs, ys;

       for(int i=0;i<n;i++){
	 xs.insert(x[i]);
	 ys.insert(y[i]);
       }

       vector<int> xvec,yvec;
       set<int>::iterator it = xs.begin(), jt = ys.begin();
       while(it!=xs.end()){
	 xvec.push_back(*it);
	 ++it;
       }
       while(jt!=ys.end()){
	 yvec.push_back(*jt);
	 ++jt;
       }

       for(int num=1;num<=n;num++){
	 //何個とるか
	 int tmpret=1 << 29;
	 for(int i=0;i<xvec.size();i++){
	   for(int j=0;j<yvec.size();j++){
	     int costs[n];
	     //ある一点を選んで
	     for(int k=0;k<n;k++){
	       costs[k] = abs(xvec[i] - x[k]) + abs(yvec[j] - y[k]);
	     }
	     //greedyに近い点を選ぶ
	     sort(costs,costs+n);
	     tmpret = min(tmpret,accumulate(costs,costs+num,0));
	   }
	 }
	 ret.push_back(tmpret);
       }
       return ret;
     }