P5963 [BalticOI ?] Card 卡牌游戏 贪心

[P5963 BalticOI ?] Card 卡牌游戏【来源请求】 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

贪心模板题。

存在$(x_1,y_1)$，$(x_2,y_2)$，假设$x_i>y_i$，显然得认为：$-x_1+y_2$是最优得的，那么有：
$$-x_1+y_2\le -x_2+y_1$$
进行不等式移项：
$$x_2+y_2\le x_1+y_1$$
由此可得：选两数和大的在减号后，两数和小的在加号后是最优的。

因此，按照两数和进行升序排序，前一半是加上两数最小值，后一半是减去两数最大值。

代码如下：

#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24