Iron Bar Cutting [DISCO Presents Discovery Channel Code Contest 2020 Qual B]

https://atcoder.jp/contests/ddcc2020-qual/tasks/ddcc2020_qual_b

解説

https://atcoder.jp/contests/ddcc2020-qual/submissions/8587116

どの切れ目を選ぶかを全探索する。
ある位置で切ったとして、片方の長さがlft, もう片方の長さがrhtであるとき、
操作を行う回数の最小値はabs(lft - rht)となる。
これを全体の総和totと今までの累積和lftを持っておくと、rht=tot-lftとなる。
回数の最小値の最小値を取ると答え。

int N; ll A[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    ll tot = 0;
    rep(i, 0, N) tot += A[i];

    ll ans = infl;
    ll lft = 0;
    rep(i, 0, N) {
        chmin(ans, abs(tot - lft - lft));
        lft += A[i];
    }
    cout << ans << endl;
}