AtCoder Regular Contest 078 C - Splitting Pile
AtCoderのC埋め2つ目。
ARC078 / ABC067 のC問題「Splitting Pile」です。a[1]からa[N]までの数字が書かれた山札(pile)を上側の数の合計と下側の数の合計の差がなるべく小さくなるようにして2つに分割(split)します。この差の絶対値を出力すればよいです。
#include <iostream> typedef long long ll; using namespace std; int main(){ int N; cin >> N; int a[N+1]; ll sum = 0LL; for(int i=1; i<=N; i++){ cin >> a[i]; sum += a[i]; } ll sunuke = 0LL; /* 0LLは「long long型の0」という意味。LLでlong long型にキャスト */ ll araiguma; ll ans = (ll) 2e10; for(int i=1; i<N; i++){ sunuke += a[i]; araiguma = sum - sunuke; ans = min(ans, abs(araiguma - sunuke)); } cout << ans << endl; return 0; }
とりあえずa[1]からa[N]までの合計をsumにとります。そんで、a[i]をi=(1→N-1)で動かして、上側の合計(sunuke=Σ(k=1→i))と下側の合計(araiguma=sum-sunuke)との差がansより小さいかなあとゆーのをやればできます。
そんで、関数abs(x)は、xの絶対値を返す関数です。便利です。if文使って3行くらいで書けるので覚えなくてもいいです。
そんじゃばいばい。
ll abs(ll x){ if(x<0) return -x; else return x; }