Ricocheting Balls [CSAcademy #73 B]

https://csacademy.com/contest/round-73/task/ricocheting-balls/

N個のボールがある。
i番目のボールの高さはH[i]mである。
このボールは下に1m/秒で落ちるが、地面に到着したら上に1m/秒の速さで上がっていく。
ある秒数でボールを止めたときの、高さの総和の最小値は？

前提知識

• 三分探索

解法

「f(t) := t秒後の高さの総和」とすると、f(t)は下に凸の関数になる。
これに気付くのが今回の問題の本質であり、後は三分探索をするだけ。

template<typename Func>
int findMin(int L, int R, Func f) { //[L, R)
    int lo = L - 1, hi = R - 1;
    while (lo + 1 != hi) {
        int mi = (lo + hi) / 2;
        if (f(mi) <= f(mi + 1)) hi = mi;
        else lo = mi;
    }
    return hi;
}




int N; ll H[101010];
//---------------------------------------------------------------------------------------------------
ll f(int t) {
    ll res = 0;
    rep(i, 0, N) res += abs(H[i] - t);
    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> H[i];

    int opt = findMin(0, 1000000001, f);
    cout << f(opt) << endl;
}