atcoder.jp
問題
提出コード(大事なとこだけ)
int main() { cout <<setprecision(10); ll N ; cin >> N; vector<ll> a(N); rep(i,N) cin >> a[i]; //ソートは出来ない。 ll S = 0; rep(i,N){ S += a[i]; } //一番好ましいのは、 S / 2 にすること ll prefer = S / 2 ; ll sunuke = 0; ll ans = INF; rep(i,N-1){ sunuke += a[i]; if(sunuke < S / 2){ chmin(ans,abs(sunuke - (S -sunuke))); }else{ chmin(ans,abs(sunuke - (S - sunuke))); //breakがあるとダメ } } cout << ans << endl; } || 解法 ・一番良いのは、どちらかの得点を S / 2 にすること (Sは整数列の総和) (この時もう片方の得点もS / 2 になる ・整数列には、負の数も与えられているので、sunuke (すぬけの得点を表す変数)がS / 2 を 初めて超えた後、またS / 2 ( prefer)に近づくこともある。 だから、一度prefer を超えたらそっから先は見ないなんてことはしなくていい。っていうかしちゃだめ。さらにいうとbreakしたからと言って最悪ケースの計算量は変わらないからするな。 -> break ; があるとダメな理由 rep(i,N-1){ の中のif条件分岐は必要ない 解説の解答 ・総和をXとして、 i枚目までの総和をxi ,とする (1 <= i <= n-1)について | xi - (X -xi) | = |X -2xi | の最小値を取ればいい