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