CF2024C#

题意简述#

给定 $n$ 个二维数组，每个数组的长度为 $2$ ，将这 $n$ 个数组连接起来，要使得数组中的逆序对数量尽可能的少。

题意分析#

题目要求排列数组使得逆序对尽可能少，对于其中一个数组，其可能贡献的逆序对数量为比 $a_{i,1}$ 小的个数 $x$ ，加上比 $a_{i,2}$ 小的个数 $y$ ，设 $cnt_i$ 为 $x+y$ ，之后只需要对数组 $cnt$ 排序输出结果即可。

注意，只要 $a_{i,1}$ 和 $a_{i,2}$ 不相同，得出的结果应该减去 $1$ ，这是因为必然会有一个数比另一个数小，所以要排除掉。

关于求解比当前数小的个数，我们可以使用二分查找函数lower_bound来求解。

Code#

1
#pragma GCC optimize(1, 2, 3, "Ofast", "inline")
2
#include <bits/stdc++.h>
3
using namespace std;
4
#define ll long long
5
#define int ll
6
#define ONLINE_JUDGE
7
#define MULTI_CASES
8
#define endl '\n'
9
const int MaxN = 2e5+100;
10
const int INF = 1e9;
11
const int mod=212370440130137957ll;
12
int T=1, N, M;
13
// int a[MaxN];
14
struct node{
15
    int x,y;
16
    int id;
17
}a[MaxN];
18
bool cmp1(node a,node b){
19
    return min(a.x,a.y)<min(b.x,b.y);
20
}
21
bool cmp2(node a,node b){
22
    return max(a.x,a.y)>max(b.x,b.y);
23
}
24
bool cmp(node a,node b){
25
    return a.id<b.id;
26
}
27
int cnt[MaxN];
28
inline void Solve()
29
{
30
  cin>>N;
31
    for(int i=1;i<=N;i++){
32
        cin>>a[i].x>>a[i].y;
33
        a[i].id=i;
34
    }
35
    vector<int>b;
36
    for(int i=1;i<=N;i++){
37
        b.push_back(a[i].x);
38
        b.push_back(a[i].y);
39
    }
40
    sort(b.begin(),b.end());
41
    for(int i=1;i<=N;i++){
42
        if(a[i].x<a[i].y){
43
            int x=lower_bound(b.begin(),b.end(),a[i].x)-b.begin();
44
            int y=lower_bound(b.begin(),b.end(),a[i].y)-b.begin()-1;
45
            cnt[i]=x+y;
46
        }
47
        else{
48
            if(a[i].x>a[i].y){
49
                int x=lower_bound(b.begin(),b.end(),a[i].x)-b.begin()-1;
50
                int y=lower_bound(b.begin(),b.end(),a[i].y)-b.begin();
51
                cnt[i]=x+y;
52
            }
53
            else{
54
                int x=lower_bound(b.begin(),b.end(),a[i].x)-b.begin();
55
                int y=lower_bound(b.begin(),b.end(),a[i].y)-b.begin();
56
                cnt[i]=x+y;
57
            }
58
        }
59
    }
60
    for(int i=1;i<=N;i++){
61
        a[i].id=cnt[i];
62
    }
63
    sort(a+1,a+N+1,cmp);
64
    for(int i=1;i<=N;i++){
65
        cout<<a[i].x<<" "<<a[i].y<<" ";
66
    }
67
    cout<<endl;
68
}
69
signed main()
70
{
71
#ifndef ONLINE_JUDGE
72
    freopen(".in", "r", stdin);
73
    freopen(".out", "w", stdout);
74
#endif
75
    ios::sync_with_stdio(0);
76
    cin.tie(0),cout.tie(0);
77

78
#ifdef MULTI_CASES
79
    cin >> T;
80
    while (T--)
81
#endif
82
       Solve();
83
    //fclose(stdin);
84
    //fclose(stdout);
85
    return 0;
86
}