题解 CF1747A 【Two Groups】

一道简单题。

将数列分为两组，其实只需要任意分配，最后大减小必为答案。

接着证明结论正确性。

对于数列 $a_1, a_2, a_3, 0, b_1, b_2, b_3(a1 \gt a_2 \gt a_3 \gt 0 \gt b_1 \gt b_2 \gt b_3)$，将其分组后，不妨设其结果为 $\lvert sum_1 \rvert - \lvert sum_2 \rvert (\lvert sum_1 \rvert > \lvert sum_2 \rvert)$ 时取到最大值，且 $sum_1 \gt 0, sum_2 \lt 0$，在 $sum_2$ 中取出一项 $b_1$，放入 $sum_1$ 中，$ans = \lvert sum_1 + b_1 \rvert - \lvert sum_2 - b_1 \rvert = \lvert sum_1 \rvert - \lvert b_1 \rvert - (\lvert sum_2 \rvert - \lvert b_1 \rvert) = \lvert sum1 \rvert - \lvert sum_2 \rvert$，与原答案相同，故得证。

#include <iostream>
#include <cmath>
#define int long long //一定要开long long！
using namespace std;
int t;
signed main() {
	ios::sync_with_stdio(false); //输入输出优化
	cin.tie(0); cout.tie(0);
	cin >> t;
	while (t--) {
		int n;
		int sum1 = 0, sum2 = 0;
		cin >> n;
		for (int i = 0; i < n; i++) {
			int x = 0;
			cin >> x;
			if (x >= 0) sum1 += x; //为方便按照正负分组
			else sum2 += x;
		}
		cout << max(abs(sum1), abs(sum2)) - min(abs(sum1), abs(sum2)) << endl; //大减小必为正解
	}
	return 0;
}

完结撒花～