自动搬运

查看原文

来自洛谷，原作者为

	Keids 时间已过了太久，等待也毫无意义。

搬运于2025-08-24 22:16:02，当前版本为作者最后更新于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_i+y_j)<(-x_j+y_i)$

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

$(x_j+y_j)<(x_i+y_i)$

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

所以我们可以得出结论：

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

代码实现也很简单，对于原序列按和从小到大排序，取前 $(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;
}