DDOSvoid's Blog

2021 ICPC Southeastern Europe Regional Contest G Max Pair Matching

发表于 分类于
本文字数： 997 阅读时长 ≈ 1 分钟

题目描述

https://codeforces.com/gym/103438/problem/G

简要题意：给定 $2n$ 个数对 $(a_i,b_i)$，现在要求将这 $2n$ 个数对分成 $n$ 组，如果 $x$ 和 $y$ 分到一组，那么这一组的贡献是 $max\lbrace|a_i-a_j|,|a_i-b_j|,|b_i-a_j|,|b_i-b_j|\rbrace$，求最大分配

Solution

不妨令 $a_i\le b_i$，我们考虑拆掉绝对值，那么这 $2n$ 个数对中，一定有 $n$ 个的贡献是 $-a_i$，另外 $n$ 个贡献是 $+b_i$

关于如何选择每个数对的是负贡献还是正贡献，我们任取两个数对来考虑，$-a_1+b_2>a_2+b_1$ 等价于 $a_1+b_1<a_2+b_2$，那么我们按照 $a_i+b_i$ 来排序，前 $n$ 个取 $-a$，后 $n$ 个取 $b$ 即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <tuple>
#include <vector>
#include <algorithm>
#define maxn 100010
#define ll long long
using namespace std;

int n;
vector<tuple<int, int, int>> vec;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; 
    for (int i = 1, x, y; i <= 2 * n; ++i) {
        cin >> x >> y; if (x > y) swap(x, y);
        vec.emplace_back(x + y, x, y); 
    } sort(vec.begin(), vec.end()); ll ans = 0; 
    for (int i = 0; i < n; ++i) ans -= get<1>(vec[i]);
    for (int i = n; i < 2 * n; ++i) ans += get<2>(vec[i]);
    cout << ans << "\n";
    return 0;
}