SRM613 Div1 Easy & Div2 Medium "TaroFriends"
問題
TopCoder Statistics - Problem Statement
訳
猫のタローは友達とゲームをして遊ぶのが好きだった。彼の友達はそれぞれ左から右への1本のライン上にいた。タローが合図を送ると、友達はいっせいにXだけ右か左に移動する。
あなたはint[] coordinatesとint Xが与えられる。coodinates[i]はi番目の猫の始めにいる位置を表す。タローが合図を送った後、左端と右端の猫の距離の最小を返せ。
制約
1 <= 友達の数 <= 50
-10^9 <= 友達の初期位置 <= 10^9
0 <= X <= 10^9
考えたこと
左側の猫は右に移動し、右側の猫は左に移動するとよさそう。後は、どの猫まで左側のグループにいれるかを決め打ちし、探索すればよい。左側に1匹も含めないパターンも忘れずに
ソースコード
class TaroFriends { public: int getNumber(vector <int> C, int X) { int n = C.size(); sort(C.begin(), C.end()); int res = 2000000000; for (int i = 0; i < n; i++) { vector <int> T = C; // right for (int j = 0; j < i; j++) { T[j] += X; } // left for (int j = i; j < n; j++) { T[j] -= X; } int l = 1000000000; int r = -1000000000; for (int j = 0; j < n; j++) { l = min(l, T[j]); r = max(r, T[j]); } res = min(res, abs(l - r)); } return res; } };