|
|
## [$P1966$ 火柴排队](https://www.luogu.com.cn/problem/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$
|
|
|
```cpp {.line-numbers}
|
|
|
#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];
|
|
|
LL 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 = 1; i <= n; i++) {
|
|
|
ans = (ans + sum(n) - sum(q[i])) % mod;
|
|
|
add(q[i], 1);
|
|
|
}
|
|
|
// 输出结果
|
|
|
printf("%lld", ans);
|
|
|
return 0;
|
|
|
}
|
|
|
``` |
