はまやんはまやんはまやん

hamayanhamayan's blog

集会所 [パソコン甲子園2019 予選 D]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0407

解説

https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0407/judge/3897181/C++14

問題へのアプローチに迷ったときは、まずは全探索を考えると良いだろう。
今回は、集会所を建てる場所を全探索する。
xの範囲が0~2000なので、この範囲で全探索する。
これ以外の所に建てるのは無駄なので、この範囲で良い。
集会所の場所を固定したときに全員が集まるのに必要な時間は、家が最大103通りある。
よって、全体で106通りくらいの計算になるが、これは問題ない。 107くらいなら間に合うと思っていればいい。

距離の計算は、差の絶対値を使うといい。
chmax, chminという独自マクロを使っているので読みにくいかもしれない。
chmax(a,b)はa=max(a,b)であるので、読み替えてほしい。

int N, X[1010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> X[i];

    int ans = inf;
    rep(shukaijo, 0, 2001) {
        int ma = 0;
        rep(i, 0, N) chmax(ma, abs(shukaijo - X[i]));
        chmin(ans, ma);
    }
    cout << ans << endl;
}