整理书籍

onlyblues / 2023-09-06 / 原文

整理书籍

书架上有若干本书排成一排。

每本书要么是大型书（用 L 表示），要么是中型书（用 M 表示），要么是小型书（用 S 表示）。

我们希望所有书能够从大到小有序排列，也就是说，所有大型书都在左侧，所有中型书都在中间，所有小型书都在右侧。

为此，你可以进行任意次交换操作，每次可以任选两本书并交换它们的位置。

请你计算，为了让所有书按要求有序排列，至少需要进行多少次交换操作。

输入格式

共一行，包含一个由 L、M、S 构成的字符串，表示初始时每个位置上的书的类型。

输出格式

一个整数，表示所需要的最少交换操作次数。

数据范围

输入字符串的长度范围 $[1,5 \times 10^5]$。

输入样例1：

LMMMS

输出样例1：

样例1解释

无需任何操作，初始排列已经符合要求。

输入样例2：

LLSLM

输出样例2：

样例2解释

一种最佳方案如下：

第一步，交换 S 和 M，序列变为 LLMLS。
第二步，交换 M 和它右边的 L，序列变为 LLLMS 。

解题思路

　　看到选择任意两个位置交换来使得序列有序，很容易想到全排列的置换群。不过要用全排列的置换群的做法的话要保证没用重复元素出现，很明显这题不适用。不过实际上还是会用到环图，做法也是很类似的。

　　令$L$，$M$，$S$分别对应$0$，$1$，$2$。假设原始序列是$a$，排序后的序列是$b$，依次遍历每一个元素，让$a_i$向$b_i$连一条边，就会得到一个环图。例如有$a=[0,0,2,0,1]$，对应的就有$b=[0,0,0,1,2]$，得到的图如下：

　　可以发现构造图的方式与构造全排列置换群是一样的，建边方式都是$p_i \to i$。不过这个问题中不同种类的元素最多只有$3$种，因此图中最多有$3$个节点（可以类比，当不同种类的元素最多有$n$种，那么图中最多有$n$个节点）。同时每个节点的入度与出度都是一样的，因为同一个值在$a$和$b$中出现的次数都一样，因此这个图也是一个欧拉图，而欧拉图也是由一堆环构成的。

　　我们最终要将序列$a$变成$b$，意味着要将图变成$n$个自环，与全排列的置换群一样，每交换两个元素最多让一个环裂变成两个环。假设当前有$m$个环，由于最终要变成$n$个自环，因此至少要交换$n-m$次。可以发现要使得$n-m$尽可能小，就要让$m$尽可能的大，即对于构造出的原图中要找到尽可能多的环。

　　可以发现在这个问题中环的长度只有三种，即长度为$1$的自环，长度为$2$的环，以及长度为$3$的大环。为此我们应该从长度最小的环开始找起，因为环的长度越小则用到的边也越少，剩的边越多得到的环可能会更多。

　　定义$3 \times 3$的矩阵$e$，其中$e_{i,j}$表示从节点$i$指向$j$的边的数量（即图的邻接矩阵表示）。那么长度为$1$的环的数量就是$e_{0,0}+e_{1,1}+e_{2,2}$，能得到长度为$2$的环的最大数量是$\min\{e_{0,1},e_{1,0}\} + \min\{e_{1,2},e_{2,1}\} + \min\{e_{0,2},e_{2,0}\}$。然后在图中删除已选出来的边，由于删边后还是保证图中每个节点的入度和出度相同，因此图中就只剩下长度为$3$的大环，且任意两点间边的数量都相同，所以长度为$3$的环的数量就是$\max\{e_{0,1},e_{1,0}\}$（可能是逆时针的大环，或是顺时针的大环，不可能同时出现否则会存在长度为$2$的环）。

　　AC代码如下，时间复杂度为$O(n \log{n})$：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 5e5 + 10;
 5 
 6 char s[N];
 7 int a[N], b[N];
 8 int e[3][3];
 9 
10 int main() {
11     scanf("%s", s);
12     int n = strlen(s);
13     for (int i = 0; i < n; i++) {
14         int t = 0;
15         if (s[i] == 'M') t = 1;
16         else if (s[i] == 'S') t = 2;
17         a[i] = b[i] = t;
18     }
19     sort(b, b + n);
20     for (int i = 0; i < n; i++) {
21         e[a[i]][b[i]]++;
22     }
23     int ret = 0;
24     for (int i = 0; i < 3; i++) {
25         ret += e[i][i];
26         for (int j = i + 1; j < 3; j++) {
27             int t = min(e[i][j], e[j][i]);
28             ret += t;
29             e[i][j] -= t, e[j][i] -= t;
30         }
31     }
32     ret += max(e[0][1], e[1][0]);
33     printf("%d", n - ret);
34     
35     return 0;
36 }

　　可以开个哈希表用计数排序优化，时间复杂度就降到了$O(n)$。AC代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 5e5 + 10;
 5 
 6 char s[N];
 7 int a[N], b[N];
 8 int e[3][3], cnt[3];
 9 
10 int main() {
11     scanf("%s", s);
12     int n = strlen(s);
13     for (int i = 0; i < n; i++) {
14         int t = 0;
15         if (s[i] == 'M') t = 1;
16         else if (s[i] == 'S') t = 2;
17         a[i] = t;
18         cnt[t]++;
19     }
20     for (int i = 0, k = 0; i < 3; i++) {
21         for (int j = 0; j < cnt[i]; j++){
22             b[k++] = i;
23         }
24     }
25     for (int i = 0; i < n; i++) {
26         e[a[i]][b[i]]++;
27     }
28     int ret = 0;
29     for (int i = 0; i < 3; i++) {
30         ret += e[i][i];
31         for (int j = i + 1; j < 3; j++) {
32             int t = min(e[i][j], e[j][i]);
33             ret += t;
34             e[i][j] -= t, e[j][i] -= t;
35         }
36     }
37     ret += max(e[0][1], e[1][0]);
38     printf("%d", n - ret);
39     
40     return 0;
41 }