P5963 [BalticOI ] Card 卡牌游戏

Keids · 2022-09-30 14:07:36 · 题解

P5963 [BalticOI ] Card 卡牌游戏

题目传送门：https://www.luogu.com.cn/problem/P5963

简述题意：给定 n 对数和一定的加减符号，每组数中取出一个进行运算，问得到的最小值是多少。

求最值，想到 dp 和贪心做法。但是仔细读题会发现,dp 无法解决这个问题，因为时间效率不行，于是思考如何贪心。

对于两组数 {x_i,y_i} 与 {x_j,y_j}，因为加减符号一定，所以我们有两种选择。

假设 x 为较大的数，y 为较小的数，那么：

情况一：-x_i+y_j；

情况二：-x_j+y_i；

假设我们取了情况一，因为满足条件，所以我们可以得到：

发现不等式两边下标不同，不妨改变一下式子的形式，将两边的 x 的位置交换一下：

这时我们就会惊奇的的发现，这不就是二者的和吗？

所以我们可以得出结论：

当一组数的和的值大于另一组时，我们选择让和大的那一组作为减数，小的那一组作为加数。

代码实现也很简单，对于原序列按和从小到大排序，取前 (n/2) 组数作为加数，后面的作为减数。

（记得开 long long）

完整代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long ll;
const int N=5e6+10;
int n;
struct node{
    ll a,b,sum;
}x[N];
bool cmp(node xw,node yw){
    return xw.sum<yw.sum;//按和排序
}
ll ans=0;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&x[i].a,&x[i].b);
        x[i].sum=x[i].a+x[i].b;
    }
    sort(x+1,x+n+1,cmp);
    for(int i=1;i<=n/2;i++){
        ans+=min(x[i].a,x[i].b);//前 n/2 个作为加数
    }
    for(int i=n/2+1;i<=n;i++){
        ans-=max(x[i].a,x[i].b);// 后面的作为减数
    }
    printf("%lld",ans);//输出结果
    return 0;
}