华为OD统一考试 - 学生重新排队

题目描述

n 个学生排成一排，学生编号分别是 1 到 n，n 为 3 的整倍数。

老师随机抽签决定将所有学生分成 m 个 3 人的小组（n == 3 * m） ，

为了便于同组学生交流，老师决定将小组成员安排到一起，也就是同组成员彼此相连，同组任意两个成员之间无其它组的成员。

因此老师决定调整队伍，老师每次可以调整任何一名学生到队伍的任意位置，计为调整了一次， 请计算最少调整多少次可以达到目标。

注意：对于小组之间没有顺序要求，同组学生之间没有顺序要求。

输入描述

第一行输入初始排队顺序序列

第二行输入分组排队顺序序列

输出描述

最少调整多少次数

用例

题目解析

本题有两个难点：

1. 如何快速判断两个小朋友是否为一组
2. 如何调整站队，才能花费次数最少

关于1，我们可以根据第二行输入做如下处理（以用例1为例）：

由于第二行输入的分组排队序列，每3个一组，因此我们只要将分组序列的各元素索引值整除3，即可得出各元素（小朋友序号）所在的分组。

即我们可以根据第二行输入，能得到一个：“序号->组号” 的映射关系。

这组映射关系，我们可以保存为一个map数组，map数组索引就是小朋友序号，map数组元素就是小朋友组号。

之后，我们再根据map的映射关系，就可以将第一行输入的初始小朋友（序号）排队顺序，映射为初始小朋友（组号）顺序，比如用例1：

初始小朋友（序号）排队顺序：4 2 8 5 3 6 1 9 7

初始小朋友（组号）排队顺序：1 1 1 2 0 0 0 2 2

之后，分组调整只需要按照 “初始小朋友（组号）排队顺序” 进行即可。

关于2，由于小朋友按3人一组，因此初始组号排队顺序可能存在如下情况：

1. 1 1 x 1 y z
2. 1 x 1 1 y z
3. 1 x 1 y 1 z

上面三种情况，我们需要让组号1的小朋友组合在一起。

对于情况1：

我们可以这样调整一次

此时分组1，不会对其他分组造成影响。比如具体示例：

• 1 1 2 1 2 2 按上面策略调整后 1 1 1 2 2 2
• 1 1 2 2 1 2 按上面策略调整后 1 1 1 2 2 2
• 1 1 2 2 2 1 按上面策略调整后 1 1 1 2 2 2

但是，如果我们像下面这样调整，需要调整2次

并且可能会影响到x的调整，比如具体示例：

• 1 1 2 1 2 2 按上面策略调整后 2 1 1 1 2 2
• 1 1 2 2 1 2 按上面策略调整后 2 2 1 1 1 2
• 1 1 2 2 2 1 按上面策略调整后 2 2 2 1 1 1

因此，对于情况1而言，最优策略是将后面的单独1并入到开头两个1中，只需要调整1次。

对于情况2：

如果将开头单独1并入后面两个2中，只需要调整一次，但是可能会对x造成影响

比如：

1 2 2 1 1 2 按照上面策略调整后 2 2 1 1 1 2，此时2还需要至少调整1次

1 2 1 1 2 2 按照上面策略调整后 2 1 1 1 2 2，此时2还需要至少调整1次

但是对于

1 2 2 2 1 1 这种情况，当前调整策略是最优的

如果将后面两个1并入到开头单独1中，那么需要调整2次

比如对于下面情况，当前调整策略是最优的

1 2 2 1 1 2 按照上面策略调整后 1 1 1 2 2 2

1 2 1 1 2 2 按照上面策略调整后 1 1 1 2 2 2

但是对于

1 2 2 2 1 1 这种情况，当前调整策略不是最优。

因此，对于情况2，我们需要判断，开头单独1和后面两个1之间是否是连续完整分组：

• 如果是，那么只需要调整一次，开头单独1并入到后面两个1中
• 如果不是，那么需要调整两次，后面两个1并入到开头单独1中

对于情况3，有如下调整策略：

可以发现，无论怎么调整都需要两次。

import Foundation

func ODTest_2_16() {
    print("两行字符串，空格分隔表示不同的学生编号。")
    print("第一行是学生目前排队情况第二行是随机抽签分组情况，从左开始每 3 个元素为一组n 为学生的数量，n 的范围为 [3, 900]，n 一定为 3 的整数倍")
    print("第一行和第二行元素的个数一定相同")
    let curOrder = (readLine() ?? "").split(separator: " ").map { Int($0) ?? 0 }
    let finalOrder = (readLine() ?? "").split(separator: " ").map { Int($0) ?? 0 }

    if finalOrder.count > 0 && curOrder.count == curOrder.count && curOrder.count % 3 == 0 {
        let noStudent = SortStudentNo(curOrder: curOrder, finalOrder: fin