1467C. Three Bags(貪心+思維)

傳送門

直接列舉最后剩下的數字在哪一個袋子里,這里以在 A A A為例

首先清楚一次操作消除 b b b,把 a a a替換成 a ? b a-b a?b

可以理解為改變 b b b的正負號,那么對一個數進行奇數次操作是負收益,偶數次操作是正收益

那么由于 a a a中有 n 1 n_1 n1?個元素,其中 n 1 ? 1 n_1-1 n1??1個元素需要作為操作中的 b b b轉移成負號出去

然后再作為 b b b轉移回來,兩次操作負負得正,所以 A A A的所有數字都是正收益

再考慮 B , C B,C B,C袋子怎么弄最優

Ⅰ. B , C B,C B,C分別剩下一個，然后分別作為 b b b給 A A A

這樣 B B B除了剩下的那個數,其余數字先給 C C C,再由 C C C給 A A A,偶數次操作是正收益

C C C同理，所以只有留下來的那個數字是負收益

不難發現讓 B , C B,C B,C把最小的數字留下來是最優的

Ⅱ . Ⅱ. Ⅱ.最后只有 B B B剩下了一個數,然后作為 b b b給 A A A

那么 B B B中的其余 n 2 ? 1 n_2-1 n2??1個元素先轉移到 C C C,然后再轉移回 B B B,再一起轉移回 A A A

都是奇數次操作,所以 B B B中的收益都是負收益, C C C中的收益都是正收益

這里 B B B中的其余 n 2 ? 1 n_2-1 n2??1個元素先轉移到 C C C,然后由 C C C直接轉移給 A A A會不會更優呢?

不需要考慮,因為這么做導致:有一部分 B , C B,C B,C是正收益,一部分是負收益

然而 Ⅰ Ⅰ Ⅰ的情況一定比這樣做更優

Ⅲ . Ⅲ. Ⅲ.最后只有 C C C剩下了一個數,然后作為 b b b給 A A A

和上面同理, B B B都是正收益, C C C都是負收益

然后代碼就很簡單了

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+10;
#define int long long
const int inf = 1e15;
int t,n1,n2,n3,a[maxn],b[maxn],c[maxn],d[maxn];
signed main()
{
	cin >> n1 >> n2 >> n3;
	int sum1 = 0,sum2 = 0,sum3 = 0;
	for(int i=1;i<=n1;i++) { cin >> a[i]; sum1 += a[i]; }
	for(int i=1;i<=n2;i++) { cin >> b[i]; sum2 += b[i]; }
	for(int i=1;i<=n3;i++) { cin >> c[i]; sum3 += c[i]; }
	sort( a+1,a+1+n1 ); sort( b+1,b+1+n2 ); sort( c+1,c+1+n3 );
	int ans1 = 0,ans2 = 0,ans3 = 0;
	ans1 = sum1+sum2+sum3-2*(b[1]+c[1]);//分別留下一個給A 
	ans2 = sum1+sum2+sum3-2*(a[1]+c[1]);	
	ans3 = sum1+sum2+sum3-2*(a[1]+b[1]);
	ans1 = max( ans1,max(sum1+sum2-sum3,sum1+sum3-sum2));//只留下一個 
	ans1 = max( ans1,sum2+sum3-sum1); 
	cout << max( ans1,max(ans2,ans3) );
}