本文主要是介绍P5963 [BalticOI ?] Card 卡牌游戏 贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
[P5963 BalticOI ?] Card 卡牌游戏【来源请求】 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
贪心模板题。
存在 ( x 1 , y 1 ) (x_1, y_1) (x1,y1)， ( x 2 , y 2 ) (x_2, y_2) (x2,y2)，假设 x i > y i x_i > y_i xi>yi，显然得认为： − x 1 + y 2 -x_1 + y_2 −x1+y2是最优得的，那么有：
− x 1 + y 2 ≤ − x 2 + y 1 -x_1 + y_2 \le -x_2 + y_1 −x1+y2≤−x2+y1
进行不等式移项：
x 2 + y 2 ≤ x 1 + y 1 x_2 + y_2 \le x_1 + y_1 x2+y2≤x1+y1
由此可得：选两数和大的在减号后，两数和小的在加号后是最优的。
因此，按照两数和进行升序排序，前一半是加上两数最小值，后一半是减去两数最大值。
代码如下：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 6e5 + 21;
struct no {int a,b;bool operator<(const no &rhs) const {return a + b < rhs.a + rhs.b;}
}a[N];
signed main()
{int n; cin>>n;for(int i = 0; i < n; ++i) cin>>a[i].a>>a[i].b;sort(a, a + n);int sum = 0;for(int i = 0; i < n / 2; ++i) {sum += min(a[i].a, a[i].b);}for(int i = n / 2; i < n; ++i) {sum -= max(a[i].a, a[i].b);}cout<<sum;
}
这篇关于P5963 [BalticOI ?] Card 卡牌游戏 贪心的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
