ABC０６７C Splitting Pile

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 | の最小値を取ればいい