【题目来源】
洛谷：[P1966 NOIP 2013 提高组] 火柴排队 - 洛谷
【题目描述】
涵涵有两盒火柴，每盒装有 \(n\) 根火柴，每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列， 同一列火柴的高度互不相同， 两列火柴之间的距离定义为：\(\sum(a_i-b_i)^2\)。
其中 \(a_i\) 表示第一列火柴中第 \(i\) 个火柴的高度，\(b_i\) 表示第二列火柴中第 \(i\) 个火柴的高度。
每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 \(10^8−3\) 取模的结果。
【输入】
共三行，第一行包含一个整数 \(n\)，表示每盒中火柴的数目。
第二行有 \(n\) 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。
第三行有 \(n\) 个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。
【输出】
一个整数，表示最少交换次数对 \(10^8−3\) 取模的结果。
【输入样例】
4
2 3 1 4
3 2 1 4
【输出样例】
1
【算法标签】
《洛谷 P1966 火柴排队》 #树状数组# #排序# #NOIP提高组# #2013#
【代码详解】
#include <bits/stdc++.h>
using namespace std;#define int long long // 使用长整型
const int N = 100005, mod = 1e8-3; // 定义常量：数组大小和模数int n; // 序列长度
int c[N]; // 离散化后的序列
int ans; // 存储最终结果
int q[N]; // 辅助数组（未使用）
int tmp[N]; // 归并排序临时数组// 结构体定义：存储数值和原始下标
struct Node
{int num; // 数值int idx; // 原始位置下标
} a[100005], b[100005]; // 两个输入序列// 比较函数：按数值升序排序
bool cmp(Node x, Node y)
{return x.num < y.num;
}/*** 归并排序并计算逆序对数量* @param l 区间左边界* @param r 区间右边界* @return 区间内的逆序对数量*/
int merge_sort(int l, int r)
{// 递归终止条件：区间长度小于1时不需要排序if (l >= r){return 0;}// 计算中点int mid = (l + r) >> 1;// 递归处理左右两半，并累加逆序对数量int res = (merge_sort(l, mid) + merge_sort(mid + 1, r)) % mod;// 归并过程int k = 0; // 临时数组指针int i = l; // 左半部分指针int j = mid + 1; // 右半部分指针while (i <= mid && j <= r){if (c[i] <= c[j]){tmp[k++] = c[i++]; // 左半元素较小，直接放入}else{tmp[k++] = c[j++]; // 右半元素较小，产生逆序对res = (res + mid - i + 1) % mod; // 统计逆序对数量}}// 处理剩余元素while (i <= mid){tmp[k++] = c[i++]; // 左半剩余元素}while (j <= r){tmp[k++] = c[j++]; // 右半剩余元素}// 将临时数组内容复制回原数组for (int i = l, j = 0; i <= r; i++, j++){c[i] = tmp[j];}return res; // 返回当前区间的逆序对总数
}signed main()
{// 输入序列长度cin >> n;// 输入序列a并记录原始位置for (int i = 1; i <= n; i++){cin >> a[i].num;a[i].idx = i;}// 输入序列b并记录原始位置for (int i = 1; i <= n; i++){cin >> b[i].num;b[i].idx = i;}// 对两个序列按数值排序sort(a + 1, a + n + 1, cmp);sort(b + 1, b + n + 1, cmp);// 建立离散化映射：将a的排名映射到b的原始位置上for (int i = 1; i <= n; i++){c[b[i].idx] = a[i].idx;}// 计算逆序对数量并输出结果cout << merge_sort(1, n);return 0;
}
【运行结果】
4
2 3 1 4
3 2 1 4
1