\(P1966\) 火柴排队
一、题目描述
涵涵有两盒火柴，每盒装有 \(n\) 根火柴，每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列， 同一列火柴的高度互不相同， 两列火柴之间的距离定义为：$ \sum (a_i-b_i)^2$
其中 \(a_i\) 表示第一列火柴中第 \(i\) 个火柴的高度，\(b_i\) 表示第二列火柴中第 \(i\) 个火柴的高度。
每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个 最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 \(10^8-3\) 取模的结果。
输入格式
共三行，第一行包含一个整数 \(n\)，表示每盒中火柴的数目。
第二行有 \(n\) 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。
第三行有 \(n\) 个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。
输出格式
一个整数，表示最少交换次数对 \(10^8-3\) 取模的结果。
样例 #1
样例输入 #1
4
2 3 1 4
3 2 1 4
样例输出 #1
1
样例 #2
样例输入 #2
4
1 3 4 2
1 7 2 4
样例输出 #2
2
提示
【输入输出样例说明一】
最小距离是$ 0$，最少需要交换 \(1\) 次，比如：交换第 $1 \(列的前\) 2$ 根火柴或者交换第 \(2\) 列的前 $2 $根火柴。
【输入输出样例说明二】
最小距离是 \(10\)，最少需要交换 \(2\) 次，比如：交换第 \(1\) 列的中间 \(2\) 根火柴的位置，再交换第 \(2\) 列中后 \(2\) 根火柴的位置。
【数据范围】
对于 \(10\%\) 的数据， \(1 \leq n \leq 10\)；
对于 \(30\%\) 的数据，\(1 \leq n \leq 100\)；
对于 \(60\%\) 的数据，\(1 \leq n \leq 10^3\)；
对于 \(100\%\) 的数据，\(1 \leq n \leq 10^5\)，\(0 \leq\) 火柴高度 \(< 2^{31}\)。
二、分析题意
首先对计算式进行转化:
\(\large \displaystyle \ \ \ \ \sum_{i=1}^{n}(a_i-b_i)^2 \\
= \sum_{i=1}^n(a_i^2+b_i^2-2a_ib_i) \\
= \sum_{i=1}^n(a_i^2+b_i^2) - \sum_{i=1}^n(2a_ib_i)
\)
可以发现,\(\large \displaystyle \sum_{i=1}^n(a_i^2+b_i^2)\)不会被排列顺序所影响。
所以，欲使原式最小，只需要使\(\large \displaystyle \sum_{i=1}^n(2a_ib_i)\)尽量大即可。
有一个 结论：
使\(\large b_i\)为\(\large b\)数组中第\(i\)大，使\(\large a_i\)为\(\large a\)数组中第\(i\)大时，对应位置相乘后的和最大。
- 证明
进行反证，假设有：\(\large a_1<a_2\),\(\large b_1<b_2\)
设存在\(\large a_1b_1+a_2b_2<a_1b_2+a_2b_1\)
则有： \(\large a_1(b_1-b_2)<a_2(b_1-b_2)\)
因为\(\large b_1-b_2<0\),则有\(a_1>a_2\)
产生矛盾，得以反证,原结论正确。
三、算法实现
先对两数组进行离散化,
由于要将 \(b\) 数组作为标准 , 来改变 \(a\) 数组的顺序
所以对离散化后数组 建立映射 , 把\(b\)数组当前排列顺序 , 当做一个升序排列的数列
即: 使 \(b_1⇒1,b_2⇒2,b_3⇒3\);
由于都已进行了离散化,再将 \(a\) 数组中的数进行更改, 按照映射关系, 为它们赋新值.
即: 使 \(a_1⇒b_i⇒j\)
然后需要将重赋值的 \(a\) 数组进行处理. 由于交换方式为相邻两元素交换
即冒泡排序,所以将其变为有序数列的代价 , 即数列中逆序对数.
使用归并排序 / 树状数组求逆序对即可
\(Code\)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;
const int mod = 99999997;
struct Node {
int x, pos;
const bool operator<(const Node &t) const {
return x < t.x;
}
} a[N], b[N];
int n;
int q[N];
int ans;
// 树状数组
int c[N];
#define lowbit(x) (x & -x)
void add(int x, int v) {
while (x < N) c[x] += v, x += lowbit(x);
}
LL sum(int x) {
LL res = 0;
while (x) res += c[x], x -= lowbit(x);
return res;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("P1966.in", "r", stdin);
#endif
scanf("%d", &n); // 火柴的数目
// 记录第一列火柴的高度，火柴的序号
for (int i = 1; i <= n; i++) scanf("%d", &a[i].x), a[i].pos = i;
// 记录第二列火柴的高度，火柴的序号
for (int i = 1; i <= n; i++) scanf("%d", &b[i].x), b[i].pos = i;
// 使用高度这个概念，进行由小到大排序
sort(a + 1, a + 1 + n);
sort(b + 1, b + 1 + n);
// 高度概念消费完毕，只能继续使用位置这个概念了
// 将一个二维的逆序对问题，转化为一维逆序对问题
// a[1].pos : 第一列中高度最小的火柴所在位置
// b[1].pos : 第二列中高度最小的火柴所在位置
// 两者之间为什么需要建立起关联？两者之间如何建立成关联？
// 可以理解为: 以前 Japan那道题，出现了多条相交的边，需要把它们梳理成互相不相交的边
// 以b为标准，将a进行调整
for (int i = 1; i <= n; i++) q[a[i].pos] = b[i].pos; // 类似于离散化
// 倒序进入树状数组,也就是最高的先来，通过前缀和，找出值比我大，但序号比我小的数量
for (int i = n; i; i--) {
ans = (ans + sum(q[i] - 1)) % mod;
add(q[i], 1);
}
// 输出结果
printf("%d", ans);
return 0;
}