Three Bags（思维）

题目 题意：给定3个背包，每个背包放置若干个数（同一书包可能放重复的数，都是正数）。现在重复若干次以下操作：分别从两个背包拿出数a和b，将b从原来的背包中消除，将a变为a-b并替换a放回原书包。现在要使3个背包最终只剩下一个数，使得这个数最大，求该值。 题解：要使数最大，那么这些背包的数尽量做正贡献，但总得有些数做负贡献。首先，我们可以想到，选取最小的数做减数最优。做一些简单的样例，找一些规律。 1、同一个背包的数可以依托于另一个背包的一个数，使得同一个背包的数都做相同的正/负贡献。如{1,2,3,4}{5}，可以{1,2,3,4}{5}->{1}{5-2-3-4}->{1+2+3+4-5}{},或者{1,2,3,4}{5}->{}{5-1-2-3-4}。 2、一个背包可以依托另一个背包的数（该数也做负贡献），只牺牲一个数，即该背包一个数做负贡献，一个数做正贡献。如{1,2,3}{4,5,6}{7}->{1-5-6}{4-2-3}{7}->{}{}{7-1+5+6-4+2+3} 结合上述规律，我们总结取最优值的两种情况：1、选取两个背包的各自最小值做负贡献，其余值做正贡献；2、选取一个总和最小的背包做负贡献，其余数做正贡献。 代码如下

#include
using namespace std;
#define ll long long
const int maxn = 300010;


int n[3];
int a[3][maxn];
int mn[3];
ll sum[3], mns;

int main() {
	
	for (int i = 0; i