0%

[NOIp2013] 火柴排队

题目

题目链接

题目大意:有两个长度为 $n$ 的序列 $a, b$,每次可以交换 $a, b$ 中相邻的两个数,最小化 $\sum(a_i - b_i)^2$。$1 \le n \le 10^5, 0 \le a_i, b_i \le 2^{31}$。

思路

首先有一个很明显的东西:$a$ 中第一大的应该跟 $b$ 中第一大的对应,$a$ 中第二大的应该跟 $b$ 中第二大的对应,以此类推。问题就转变为如何将 $b$ 的大小顺序变为 $a$ 的大小顺序。

先离散化一下。

之后相当于把 $b$ 变成 $a$,相当于按照 $a$ 的顺序对 $b$ 数组排序。

我们可以设 $c_{b_i} = a_i$,那么问题就变为了对 $c$ 冒泡排序的次数,求逆序对即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return ;
}

typedef long long LL;

const LL mod = 1e8 - 3;

LL A[100010], B[100010], a[100010], b[100010], c[100010], t[100010];
LL ans;
int n;

inline int lowbit(int x) { return x & -x; }

LL query(int x) {
LL s = 0;
while (x) {
s += t[x];
x -= lowbit(x);
}
return s;
}

void modify(int x, LL p) {
while (x <= n) {
t[x] += p;
x += lowbit(x);
}
return ;
}

int main() {
read(n);
for (int i = 1; i <= n; ++i) read(A[i]), a[i] = i;
for (int i = 1; i <= n; ++i) read(B[i]), b[i] = i;
std::sort(a + 1, a + n + 1, [](int a, int b) {
return A[a] < A[b];
} );
std::sort(b + 1, b + n + 1, [](int a, int b) {
return B[a] < B[b];
} );
for (int i = 1; i <= n; ++i) c[b[i]] = a[i];
for (int i = n; i >= 1; --i) {
ans += query(c[i] - 1);
modify(c[i], 1);
ans %= mod;
}
printf("%lld\n", ans % mod);
return 0;
}