問題
http://community.topcoder.com/stat?c=problem_statement&pm=9976&rd=13514
（x、y）の点がN個与えられる。
この点を１個～N個までそれぞれ同じ位置にあるよう移動させるときの、
それぞれの最小移動数を求める。
解き方
各点の移動距離が最小となるx、y座標は、
与えられたx、y座標のいずれかになる。
よって、与えられたx、y座標のすべてを始点としたときの
移動距離が最小のものを更新していって求める。
コード
class TheTower {
public: vector<int> count(vector<int> x, vector<int> y) {
int n=x.size();
vector<int> ans(n,1e+9);
FORE(i,0,n)FORE(j,0,n){
vector<int> vx;
FORE(k,0,n)vx.push_back(abs(x[i]-x[k])+abs(y[j]-y[k]));
sort(all(vx));
int sum=0;
FORE(k,0,n){
sum+=vx[k];
ans[k]=min(ans[k],sum);
}
}
return ans;
}
};
public: vector<int> count(vector<int> x, vector<int> y) {
int n=x.size();
vector<int> ans(n,1e+9);
FORE(i,0,n)FORE(j,0,n){
vector<int> vx;
FORE(k,0,n)vx.push_back(abs(x[i]-x[k])+abs(y[j]-y[k]));
sort(all(vx));
int sum=0;
FORE(k,0,n){
sum+=vx[k];
ans[k]=min(ans[k],sum);
}
}
return ans;
}
};
Share this
Related Posts
SRM 538 DIV1 Easy - EvenRoute
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11808&rd=14729
解き方
（ｘ，ｙ）の合計が奇数の座標と偶数の座標が存- SRM 402 DIV1 Easy - RandomSort
問題
http://community.topcoder.com/stat?c=problem_statement&pm=8590&rd=12174
解き方
全探索可能。
配列の状態を持つのでdpではなく
- SRM 502 DIV1 Easy - TheLotteryBothDivs
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11359&rd=14431
解き方
初期配列のままで各文字列ペアについて包含して
- SRM 577 DIV1 Easy - EllysRoomAssignmentsDiv1
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12514&rd=15497
解き方
部屋の数Rから、部屋への割り当てが行われる回