[NOIP2013 提高组] 火柴排队

题目描述

涵涵有两盒火柴，每盒装有 $n$ 根火柴，每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列， 同一列火柴的高度互不相同， 两列火柴之间的距离定义为：$\sum (a_i-b_i)^2$。

其中 $a_i$ 表示第一列火柴中第 $i$ 个火柴的高度，$b_i$ 表示第二列火柴中第 $i$ 个火柴的高度。

每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 $10^8-3$ 取模的结果。

对于 $100%$ 的数据，$1 \leq n \leq 10^5$，$0 \leq$ 火柴高度 $< 2^{31}$。

分析

依题意模拟即可

注意到，可以随意对两个数组进行排序。

分析可知若需要 $\sum (a_i-b_i)^2$ 最小，可以让两数组都有序（单调性相同）。

如果考虑对两个数组都进行若干次交换，情况太复杂了。

发现这完全可以转化为只对其中一个数组的交换（比如说 $b_i$）。

又注意到，这两个数组的对应位置是相对独立的，那么有以下做法：

  • 对 $b_i$ 进行若干次交换，使得 $b_i$ 作为第 $k$ 大的数与 $a_i$ 同样也是第 $k$ 大的数相对应。
  • （第 $k$ 大指相对于各自的数组）

但是 $a_i$ 不是有序的，这是如果对 $b_i$ 进行排序，会很难处理，考虑进行转化。

假设 $a_i$ 一开始就是有序的，那么只需要对 $b_i$ 从小到大排序即可。

答案就是 $b_i$ 中逆序对的数量，用树状数组维护。

如何进行转化呢？ 需要重新指定数字间的大小关系。

关系是什么呢？ 从 $a_i$ 来。

如果认为 $a_i$ 是第 $i$ 小的数，就可以以此对 $b_i$ 进行排序了。

不要忘了进行离散化！（把值域缩到 $[1, n]$）

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
const int mod = (114514+114514)*(-11+451-4)+114514+114*51*4+114*51+4+1/1-4+51*4;

int n, ans;
int a[N], b[N], to[N];

struct bitree{
    int c[N], res;
    inline int lb(int x) { return x & (-x); }
    inline void add(int x, int v){
        for (; x <= n; x += lb(x))
            c[x] += v;
    }
    inline int find(int x){
        for (res = 0; x; x -= lb(x))
            res += c[x];
        return res;
    }
    inline int find(int x, int y){
        return find(y) - find(x - 1);
    }
}tr;

map<int, int> mpa, mpb;

signed main(){
    
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i], mpa[a[i]] = i;
    
    for (int i = 1; i <= n; i++)
        cin >> b[i], mpb[b[i]] = i;
    
    sort(a + 1, a + 1 + n); sort(b + 1, b + 1 + n);
    
    for (int i = 1; i <= n; i++)
        to[mpa[a[i]]] = mpb[b[i]];
    
    for (int i = 1; i <= n; i++){
        ans = (ans + tr.find(n - to[i])) % mod;
        tr.add(n - to[i] + 1, 1);
    }
    
    cout << ans;
    
    
    return 0;
}

Written with StackEdit中文版.