AtCoder Beginner Contest 067 C - Splitting Pile

問題

beta.atcoder.jp

数字が書いてあるカードを差分が最小になるように二人で分け合うにはどうすればよいか

考察

カード全体の累積和をまず求める。
N枚のときの累積和と（カード全体の累積和 - N枚のときの累積和)の差分をとり、最小の数を求めればおーけー。

コード

#include <iostream>
#include <algorithm>

#define ll long long
int L = 2000000007;
using namespace std;
ll a[200050] = {};
ll sum[200050] = {};
int main()
{
	ll n;
	ll ans = L;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	sum[0] = 0;

	for (int i = 0; i < n; i++)
	{
		sum[i + 1] = a[i] + sum[i];
	}
	ll Max = sum[n];

	for (int i = 1; i < n; i++)
	{
		ll acm = abs(sum[i] - (Max - sum[i]));

		ans = min(ans, acm);
	}

	cout << ans << endl;
}

累積和はO(N)でいけるからとても便利