华为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: finalOrder)
        noStudent.sortNo()
        print("最少调整多少次数")
        print("\(noStudent.movedCount)")
    }
}

// 分块（即连续的相同组的小朋友）
class OrderCount {
    var order: Int = 0
    var count: Int = 0

    init(order: Int, count: Int) {
        self.order = order
        self.count = count
    }
}

class SortStudentNo {
    init(curOrder: [Int], finalOrder: [Int]) {
        self.n = curOrder.count
        self.curOrder = curOrder
        self.finalOrder = finalOrder
    }

    // 学生总数
    var n = 0
    // 学生编号与组号的映射关系
    var relations: [Int: Int] = [:]
    var finalOrder: [Int] = []
    var curOrder: [Int] = []
    // 记录调整位置次数
    var movedCount = 0

    func sortNo() {
        movedCount = 0

        // 序号->组号 映射关系
        for i in 0 ..< n {
            relations[finalOrder[i]] = i / 3
        }
        // 初始小朋友（组号）排队顺序
        let orders = curOrder.map { relations[$0] ?? -1 }

        // key是组号，val是对应组号的小朋友分块
        var blocks: [Int: [OrderCount]] = [:]

        // 按初始排队顺序记录分块
        // 相邻相同组号合并为块
        var queue: [OrderCount] = []

        orders.forEach { order in
            if queue.isEmpty || queue.last?.order != order {
                let item = OrderCount(order: order, count: 1)
                queue.append(item)
                if blocks[order] == nil {
                    blocks[order] = []
                }
                blocks[order]?.append(item)
            } else {
                queue.last?.count += 1
            }
        }

        while !queue.isEmpty {
            let first = queue.removeFirst()
            // 如果开头块是空的，或者开头块已经包含3个小朋友，那么不需要调整位置
            if first.count == 0 || first.count == 3 { continue }

            if queue.isEmpty { break }

            var second = queue.first
            while second?.count == 0 {
                queue.removeFirst()
                second = queue.first
            }

            // 如果开头块和第二块组号相同，则合并（前面并入后面）
            if first.order == second?.order {
                second?.count += first.count
                continue
            }

            /* 如果开头块和第二块组号不同，则进入具体情况分析 */
            if first.count == 2 {
                // 开头块有2个小朋友，则情况如下组号1例子，此时需要将后面的单独1，并入开头两个1中，即调整一次
                // 1 1 x 1
                movedCount += 1
                // 后面单独1所在块的小朋友数量清空
                blocks[first.order]?.forEach { item in
                    item.count = 0
                }
                continue
            }

            if first.count == 1 {
                // 开头块只有1个小朋友，则有两种情况
                if blocks[first.order]?.count == 3 {
                    // 对于组号的分块有三个，即如下组号1例子
                    // 1 x 1 y 1 z
                    // 此时需要将后面两个单独1，并入到开头1中，即调整两次
                    movedCount += 2
                    // 后面两个单独1所在块的小朋友数量清空
                    blocks[first.order]?.forEach { item in
                        item.count = 0
                    }
                } else {
                    // 对于组号的分块有两个，则如下组号1例子
                    // 1 x 1 1
                    // 此时需要将开头单独1并入到后面两个1中，即调整一次
                    movedCount += 1
                    // 后面两个1所在块的小朋友数量变为3个
                    blocks[first.order]?.forEach { item in
                        item.count = 3
                    }
                }
            }
        }
    }
}