WARush

SRMの結果とか、解けた問題のコードを書いていきます

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;
    }
};