会议座位

题意

先给出老师们原来的座位顺序，再给出打乱后的座位顺序。

如果有一对老师 a、b，原来是 a 在 b 左边，现在变成 a 在 b 右边，那么这对老师贡献 1 单位不满值。

要求输出总不满值。

思路

先看一个可以直接验证想法的朴素解：

cpp

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

typedef long long ll;

const int MAXN = 2005;

int n;
int a[MAXN];
map<string, int> pos;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        string name;
        cin >> name;
        pos[name] = i;
    }

    for (int i = 1; i <= n; i++) {
        string name;
        cin >> name;
        a[i] = pos[name];
    }

    ll answer = 0;

    // brute.cpp：转成原序列下标后，直接枚举所有下标对统计逆序对。
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (a[i] > a[j]) {
                answer++;
            }
        }
    }

    cout << answer << '\n';
    return 0;
}

如果直接在打乱后的序列里枚举所有老师对，判断他们相对顺序是否和原来相反，复杂度是 $O(n^2)$ ，肯定不行。

关键是把名字问题转成整数问题。

先把原来的座位顺序记下来：

第一个老师的位置记为 1
第二个老师的位置记为 2
…

用一个 map<string, int> 记录“名字 -> 原位置”。

然后把打乱后的序列改写成“原位置编号序列”。

例如原序列是：

text

1Stan Kyle Kenny

位置编号就是：

text

1Stan -> 1, Kyle -> 2, Kenny -> 3

打乱后如果是：

text

1Kyle Stan Kenny

就会变成：

text

12 1 3

此时题目要求的“不满值”，就恰好变成这个整数序列里的逆序对数量。

所以整题转化成标准逆序对问题，再用归并排序统计即可。

代码

cpp

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
63
64
65
66
67
68
69
70
71#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 100005;

int n;
int a[MAXN];
int tmp[MAXN];
ll answer;
map<string, int> pos;

void merge_sort_count(int l, int r) {
    if (l >= r) {
        return;
    }

    int mid = (l + r) >> 1;
    merge_sort_count(l, mid);
    merge_sort_count(mid + 1, r);

    int i = l;
    int j = mid + 1;
    int k = l;

    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            tmp[k++] = a[i++];
        }
        else {
            tmp[k++] = a[j++];
            answer += (ll)(mid - i + 1);
        }
    }

    while (i <= mid) {
        tmp[k++] = a[i++];
    }
    while (j <= r) {
        tmp[k++] = a[j++];
    }

    for (int p = l; p <= r; p++) {
        a[p] = tmp[p];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        string name;
        cin >> name;
        pos[name] = i;
    }

    for (int i = 1; i <= n; i++) {
        string name;
        cin >> name;
        a[i] = pos[name];
    }

    answer = 0;
    merge_sort_count(1, n);

    cout << answer << '\n';
    return 0;
}

复杂度

建立名字到位置的映射： $O(n log n)$
归并排序统计逆序对： $O(n log n)$

总时间复杂度： $O(n log n)$ ，空间复杂度： $O(n)$ 。

总结

这题表面上是字符串和座位顺序，核心其实是：

用映射把名字转成原始排名编号
把“相对顺序颠倒”改写成逆序对
用归并排序统计答案

看出“先映射，再数逆序对”，题目就回到熟悉模板了。

目录

题意

思路

代码

复杂度

总结