题解：CF725F Family Photos

2021sunzishan · 2025-07-29 22:49:28 · 题解

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

翻译是*。

题目大意：

有 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 赚更多会把第二张取掉。

• 如果谁先手都会亏，即 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 交替取就行了。非常细节的问题就不加以解释了，想想就会了（本菜鸡就是这样）。

代码:

#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;
}

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