505. 洋火列队-逆序对模板题

涵涵有两盒洋火，每盒装有 nn 根洋火，每根洋火都有一个高度。
现在将每盒中的洋火各自排成一列，同一列洋火的高度互不雷同，两列洋火之间的距离界说为：

∑i=1n(ai−bi)2∑i=1n(ai−bi)2
此中 aiai 表现第一列洋火中第 ii 个洋火的高度，bibi 表现第二列洋火中第 ii 个洋火的高度。 
每列洋火中相邻两根洋火的位置都可以交换，请你通过交换使得两列洋火之间的距离最小。
请问得到这个最小的距离，最少必要交换多少次？
如果这个数字太大，请输出这个最小交换次数对 99,999,99799,999,997 取模的结果。
输入格式

共三行，第一行包含一个整数 nn，表现每盒中洋火的数目。 
第二行有 nn 个整数，每两个整数之间用一个空格隔开，表现第一列洋火的高度。
第三行有 nn 个整数，每两个整数之间用一个空格隔开，表现第二列洋火的高度。
输特殊式

输出共一行，包含一个整数，表现最少交换次数对 99,999,99799,999,997 取模的结果。
数据范围

1≤n≤1051≤n≤105,
0≤洋火高度≤231−10≤洋火高度≤231−1
输入样例：

1. 4
2. 2 3 1 4
3. 3 2 1 4

复制代码

输出样例：

1. 1

复制代码

 

1. #include <bits/stdc++.h> // 包含所有标准库头文件
3. using namespace std; // 使用标准命名空间
5. // 定义常量：数组的最大长度为1e5 + 10，模数为99999997
6. const int N = 1e5 + 10, MOD = 99999997;
8. int n; // 数组的大小
9. int a[N], b[N], c[N], p[N]; // 定义四个数组，分别用于存储原始数据和中间结果
11. // 函数work对数组进行排序，并通过辅助数组p完成a和b的第一步操作
12. void work(int a[]) {
13.     //  for(int i=0; i<n;i++)
14.     // {
15.     //     cout<<a[i]<<' ';
16.     // }
17.     // cout<<endl;
18.     // 初始化辅助数组p，存储每个元素的原始索引
19.     for (int i = 0; i < n; i++) p[i] = i;
21.     // 根据数组a的值对p中的索引进行排序
22.     sort(p, p + n, [&](int x, int y) {
23.         return a[x] < a[y]; // 按照a数组中对应位置的值从小到大排序
24.     });
25.     // for(int i=0; i<n;i++)
26.     // {
27.     //     cout<<p[i]<<' ';
28.     // }
29.     // cout<<endl;
30.     // 根据排序后的p重新调整a数组的值，使得a数组变为从0到n-1的排列
31.     for (int i = 0; i < n; i++) a[p[i]] = i;
32.     //  for(int i=0; i<n;i++)
33.     // {
34.     //     cout<<a[i]<<' ';
35.     // }
36.     // cout<<endl;
37. }
39. // 归并排序函数，用于计算逆序对数量并对数组b进行排序
40. int merge_sort(int l, int r) {
41.     if (l >= r) return 0; // 如果区间长度小于等于1，直接返回0
43.     // 计算中间点mid，将区间[l, r]分为左右两部分
44.     int mid = l + r >> 1;
46.     // 递归地对左右两部分进行归并排序，并累加逆序对数量
47.     int res = (merge_sort(l, mid) + merge_sort(mid + 1, r)) % MOD;
49.     // 合并左右两部分时计算跨区间的逆序对数量
50.     int i = l, j = mid + 1, k = 0;
51.     while (i <= mid && j <= r) { // 当左右两部分都有未处理的元素时
52.         if (b[i] <= b[j]) { // 如果左边的元素小于等于右边的元素
53.             p[k++] = b[i++]; // 将左边的元素加入临时数组p
54.         } else { // 如果右边的元素小于左边的元素
55.             p[k++] = b[j++]; // 将右边的元素加入临时数组p
56.             // 计算以当前右边元素为结尾的逆序对数量
57.             res = (res + mid - i + 1) % MOD;
58.         }
59.     }
61.     // 处理剩余的左半部分
62.     while (i <= mid) p[k++] = b[i++];
64.     // 处理剩余的右半部分
65.     while (j <= r) p[k++] = b[j++];
67.     // 将临时数组p中的结果拷贝回数组b
68.     for (int i = l, j = 0; i <= r; i++, j++) b[i] = p[j];
70.     return res; // 返回逆序对总数
71. }
73. int main() {
74.     // 输入数组大小n
75.     cin >> n;
77.     // 输入数组a
78.     for (int i = 0; i < n; i++) cin >> a[i];
80.     // 输入数组b
81.     for (int i = 0; i < n; i++) cin >> b[i];
83.     // 对数组a和b分别进行排序操作（调用work函数）
84.     work(a), work(b);
86.     // 通过a数组生成c数组，c[a[i]] = i 表示a数组中值为a[i]的元素在排序后的位置是i
87.     for (int i = 0; i < n; i++) c[a[i]] = i;
89.     // 通过c数组更新b数组，b[i] = c[b[i]] 表示将b数组中的每个值映射为它在排序后的a数组中的相对位置
90.     for (int i = 0; i < n; i++) b[i] = c[b[i]];
92.     // 调用merge_sort函数计算b数组中的逆序对数量，并输出结果
93.     cout << merge_sort(0, n - 1) << endl;
95.     return 0; // 程序结束
96. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。