题解：CF725F Family Photos

好妙好可爱的贪心啊，只是我太弱想不完，还要学长的提示。

翻译是*。

题目大意：

有

n

组照片，每组照片有两张，第一张对于

a,b

的贡献分别为

a_1,b_1

，第二张为

a_2,b_2

，取了第一张才能取第二张。两人都采取最优策略使自己的贡献和比对方尽可能大得多，问最后

a

和

b

的差值。

思路：

对于一组照片:

1.对于

a_1-b_2\le a_2-b_1

的情况，即后手更优（或者一样）：

我们假设 $0<a_1-b_2<a_2-b_1$ ，则也有 $b_1-a_2<b_2-a_1<0$ 。那么不管 $a$ 是先手还是后手都是稳赚不赔， $b$ 都是亏。那么我们不妨把这些照片组放在后面， $a$ 没有其它选的时候就必然选第一张了，而 $b$ 为防止 $a$ 赚更多会把第二张取掉。
$0<b_1-a_2<b_2-a_1$ 的情况同理， $b$ 先手就好了。
如果谁先手都会亏，即 $a_1-b_2\le0,b_1-a_2\le0$ ，那这牌就废了，傻子才取。

2.对于

a_1-b_2>a_2-b_1

的情况，即先手更优：

先假设如果每组只有一张照片，那么就是 $a$ 和 $b$ 交替取。若取第 $i$ 组比取第 $j$ 组好，当且仅当 $a_i-b_j>a_j-b_i,b_i-a_j>b_j-a_i$ 即 $a_i+b_i>a_j+b_j$ ，排个序就可以了。
那一组照片其实就可以拆开成两张了，因为第一张 $a,b$ 的和总是大于第二张，所以排序后总是先取 $1$ 再取 $2$ ，非常满足条件，然后 $a,b$ 交替取就行了。非常细节的问题就不加以解释了，想想就会了（本菜鸡就是这样）。

代码:

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 200005//拆成两张双倍空间 
int n;
struct node{
	int a,b;
}a[N];
inline int read(){
	int a=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		a=a*10+c-'0';
		c=getchar();
	}
	return a*f;
}
bool cmp(node a,node b){
	return a.a+a.b>b.a+b.b;
} 
main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read();
	int ans=0,cnt=0;
	for(int i=1;i<=n;i++){
		int a1=read(),b1=read(),a2=read(),b2=read();
		if(a1-b2>a2-b1){//先手优，先存起来，两张照片分开 
			a[++cnt].a=a1,a[cnt].b=b1;
			a[++cnt].a=a2,a[cnt].b=b2;
			continue;
		}
		if(a1-b2<=0&&b1-a2<=0)continue;//后手优，但先手<=0，不取
		if(0<a1-b2)
			ans+=a1-b2;//a先手>0 
		else
			ans+=a2-b1;//b先手>0 
	}
	sort(a+1,a+1+cnt,cmp);
	for(int i=1;i<=cnt;i++){//交替给a和b 
		if(i%2)
			ans+=a[i].a;
		else
			ans-=a[i].b;
	}
	printf("%lld\n",ans);
	return 0;
}

希望自己能记住这题，这题解写得不容易，这题也不容易。

题解：CF725F Family Photos

文章操作

题目大意：

思路：

代码:

相关推荐

评论

题解：CF725F Family Photos