Codeforces Round 980 (Div. 2) C. Concatenation of Arrays

题目：

给定 n 个数组 a1, a2, …, an。每个数组的长度都是2。因此，ai=[ai,1, ai,2]。你需要将这些数组连接成一个长度为 2n 的单一数组，以便使结果数组中的逆序数最小。注意，你不需要实际计算逆序的数量。

更正式地说，你需要选择一个长度为 n 的排列 p，使得数组 b=[ap1,1, ap1,2, ap2,1, ap2,2,…, apn,1, apn,2] 中的逆序数尽可能少。

数组 c 中的逆序数是指索引对 i 和 j 的数量，其中 i<j 且 ci>cj。

长度为 n 的排列是由 n 个不同整数从 1 到 n 随机顺序组成的数组。例如，[2,3,1,5,4] 是一个排列，但 [1,2,2] 不是一个排列（2 在数组中出现了两次），而 [1,3,4] 也不是一个排列（n=3，但数组中有 4）。

思路：

涉及逆序对那就要考虑排序，而怎么排序是一个贪心问题。对所有数对依据每个数对中两个数的较小的那个数进行升序排列，如果较小值相等，则按照较大值升序排列。

代码：

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define MOD 1000000007
#define fi first
#define se second
#define pii pair<int, int>
#define vec vector

bool cmp(pii a, pii b){
    int ma = min(a.fi, a.se), mb = min(b.fi, b.se);
    if(ma != mb){
        return ma < mb;
    }
    ma = max(a.fi, a.se), mb = max(b.fi, b.se);
    return ma < mb;
}

void solve(){   
    int n;
    cin >> n;
    vec<pii> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i].fi >> a[i].se;
    }
    sort(a.begin(), a.end(), cmp);
    for(int i = 0; i < n; i++){
        cout << a[i].fi << ' ' << a[i].se << ' ';
    }
    cout << '\n';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}