Codeforces Round #695 (Div. 2) C. Three Bags (贪心,思维)

题意:有三个背包,每个背包里都用一些数字,你可以选择某一个背包的数字\(a\),从另外一个背包拿出\(b\)(拿出之后就没有了),然后将\(a\)替换为\(a-b\),你可以进行任意次这样的操作,使得最后只剩下一个数,问这个数最大能是多少.
题解:我的思路是,先任意选两个背包,假设\(x\)和\(y\),我们假设选\(x\)中的最大值,\(y\)中的最小值,很明显,我们让\(y\)的最小值减去没有选的背包的所有数和除了\(x\)最大值的所有数一定是最优的,但是\(y\)中除了最小值的其他数不好处理,这里我们可以先让\(x\)中的最小值减去\(y\)除了最小值的其他数,因为小的减大的可以使贡献损失最小,这里要注意,假如减完后,\(x\)的最小值是正数,那么我们让\(y\)的最小值直接减去\(x\)操作后最小值即可,如果是负数的话,我们就要将这个数减到没有用过的那个背包里面,然后再用\(y\)的最小值减去没有选的背包的所有数,其实这里我们只要加一个绝对值就可以了,最后的最大值就是用\(x\)中的最大值减去操作后的\(y\)中的最小值.因为只有三个背包,所以一共有\(6\)种情况,我们一一列举维护一个最大值就好了.
代码:

#include <bits/stdc++.h>

#define ll long long

#define fi first

#define se second

#define pb push_back

#define me memset

#define rep(a,b,c) for(int a=b;a<=c;++a)

#define per(a,b,c) for(int a=b;a>=c;--a)

const int N = 1e6 + 10;

const int mod = 1e9 + 7;

const int INF = 0x3f3f3f3f;

using namespace std;

typedef pair<int,int> PII;

typedef pair<ll,ll> PLL;

ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}

ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}

int n1,n2,n3;

ll s1,s2,s3;

int main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin>>n1>>n2>>n3;

	vector<ll> a(n1),b(n2),c(n3);

	for(auto &w:a) cin>>w,s1+=w;

	for(auto &w:b) cin>>w,s2+=w;

	for(auto &w:c) cin>>w,s3+=w;

	n1--,n2--,n3--;

	sort(a.begin(),a.end());

	sort(b.begin(),b.end());

	sort(c.begin(),c.end());

	ll ans=0;

	//max_1,min_2

	ll sum1=s1-a[n1]-a[0];

	ll sum2=s2-b[0];

	ll sum3=s3;

	ans=max(ans,a[n1]-(b[0]-sum3-sum1-abs(a[0]-sum2)));

	//max_1,min_3

	sum1=s1-a[n1]-a[0];

	sum2=s2;

	sum3=s3-c[0];

	ans=max(ans,a[n1]-(c[0]-sum2-sum1-abs(a[0]-sum3)));

	//max_2,min_1

	sum1=s1-a[0];

	sum2=s2-b[n2]-b[0];

	sum3=s3;

	ans=max(ans,b[n2]-(a[0]-sum3-sum2-abs(b[0]-sum1)));

	//max_2,min_3

	sum1=s1;

	sum2=s2-b[n2]-b[0];

	sum3=s3-c[0];

	ans=max(ans,b[n2]-(c[0]-sum1-sum2-abs(b[0]-sum3)));

	//max_3,min_1

	sum1=s1-a[0];

	sum2=s2;

	sum3=s3-c[n3]-c[0];

	ans=max(ans,c[n3]-(a[0]-sum2-sum3-abs(c[0]-sum1)));

	//max_3,min_2

	sum1=s1;

	sum2=s2-b[0];

	sum3=s3-c[n3]-c[0];

	ans=max(ans,c[n3]-(b[0]-sum1-sum3-abs(c[0]-sum2)));

	cout<<ans<<'\n';

    return 0;

}

巴特西

Codeforces Round #695 (Div. 2) C. Three Bags (贪心,思维)

最新文章

热门文章