Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-08-15SRM300台を練習していく part9

SRM 324 TournamentPlan

|  SRM 324 TournamentPlan - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 324 TournamentPlan - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6807

プレイヤーが2回以上移動するのは損なので、全てのプレイヤーが一堂に会する形にしたい。

はじめは最小全域木作るだけかなと思ったけど、それだとサンプルが通らない。

各プレイヤーの初期位置のXとYにそれぞれついて、

地点の候補として各プレイヤーからの距離を計算し、和を返すだけだった。


public class TournamentPlan {
	public int getTravelDistance(int[] street, int[] avenue) {
		int len = street.length;
		int dx = 999999999;
		int dy = 999999999;
		for (int i = 0 ; i < len ; i++) {
			int d = 0;
			for (int j = 0 ; j < len ; j++) {
				d += Math.abs(street[i] - street[j]);
			}
			dx = Math.min(dx, d);
		}
		for (int i = 0 ; i < len ; i++) {
			int d = 0;
			for (int j = 0 ; j < len ; j++) {
				d += Math.abs(avenue[i] - avenue[j]);
			}
			dy = Math.min(dy, d);
		}
		return dx + dy;
	}
}