「要是我那关于生命的歌能使你珍惜生命就好了」

FutaRimeWoawaSete · 2022-11-16 11:06:14 · 题解

sol of CF725F

注意题意，要求先选一对的第一张才能选第二张，不知道多少人被这 shaber 翻译祸害了。

第一眼感觉很像阿狸与桃子那道题。

我们先进行两次大的分类讨论：

不难想到对于第二类情况的约束性更强，对于第二类情况我们继续分讨：

• 可以证明上述两种情况在满足第二类大情况的前提下是不会一起出现的，否则会与第二类大情况的前提矛盾。

• 剩余的情况是 a_1 - b_2 \leq 0 且 b_1 - a_2 \leq 0，则此时该对照片永远不会被选择。

发现第二类大情况的贡献独立，我们只需要考虑第一类大情况即可，设剩余 x 对这样的照片。

将 2\times x 张照片的值先都加上 \frac{(a-b)}{2} 的贡献，将每张照片剩余的价值 \frac{a+b}{2} 放入一个数组中降序排序，然后奇偶交题选择，若被 A 选到就加上 \frac{a+b}{2} 否则减去 \frac{a+b}{2}。

可以发现这样处理每张照片的贡献都是 +a 或 -b 的形式，并且由于 a_1 - b_2 \geq a_2 - b_1，降序排序后若已经决策到了一对照片的第二张照片，第一张照片已经被决策过了也是合法的选择。

/*
2
5 1
0 -6
*/
#include "bits/stdc++.h"
using namespace std;
#define ll long long
const int Len = 2e5 + 5;
int n,m,ct;
double p[Len];double as;
int main()
{
    scanf("%d",&n);
    for(int i = 1 ; i <= n ; i ++)
    {
        int a1,b1,a2,b2;scanf("%d %d %d %d",&a1,&b1,&a2,&b2);
        if(a1 + b1 >= a2 + b2) 
        {
            as += 1.0 * (a1 - b1) / 2.0 , as += 1.0 * (a2 - b2) / 2.0;
            p[++ ct] = 1.0 * (a1 + b1) / 2.0;
            p[++ ct] = 1.0 * (a2 + b2) / 2.0;
        }
        else if(a1 > b2) as += a1 - b2;
        else if(b1 > a2) as += a2 - b1;
    }
    sort(p + 1 , p + 1 + ct);int opt = 0;
    for(int i = ct ; i >= 1 ; i --) 
    {
        opt ^= 1;
        if(opt) as += p[i];
        else as -= p[i];
    }
    printf("%.0lf\n",as);
    return 0;
}