华为OD机试真题 - 小朋友分组最少调整 (D卷,200分)

题目描述

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

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

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

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

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

目录

题目描述

输入描述

输出描述

用例

题目解析

Java算法源码

JS算法源码

Python算法源码

C算法源码

华为机试有三道题目，第一道和第二道属于简单或中等题，分值为100分，第三道为中等或困难题，分值为200分。总分为400分，150分钟，机试是在牛客考试，练习的时候也可以在牛客网练习，提前熟悉操作

https://ac.nowcoder.com/acm/contest/5652/K

点击上方链接进入牛客练习界面，可以自定义题目，自定义输入、输出等等，华为OD真实机试环境，非其他第三方平台模拟。

输入描述

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

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

输出描述

最少调整多少次数

用例

题目解析

1. 首先将输入的初始排队顺序序列和分组排队顺序序列转换为列表，例如输入为"4 2 8 5 3 6 1 9 7"和"6 3 1 2 4 8 7 9 5"，则初始排队顺序列表为[4, 2, 8, 5, 3, 6, 1, 9, 7]，分组排队顺序列表为[6, 3, 1, 2, 4, 8, 7, 9, 5]。
2. 初始化一个变量count用于记录调整次数。
3. 遍历分组排队顺序列表，对于每个小组，检查初始排队顺序中对应的三个学生是否已经满足要求（即同组学生之间没有顺序要求），如果不满足，则进行以下操作： a. 找到当前小组在初始排队顺序中的起始位置start_index。 b. 计算当前小组在初始排队顺序中的结束位置end_index。 c. 将当前小组的学生按照分组排队顺序重新排列。 d. 将重新排列后的学生插入到初始排队顺序的start_index位置，并将原来start_index位置及其之后的学生向后移动。 e. 更新count的值。
4. 最后输出count作为结果。

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    let nums = (await readline()).split(" ").map(Number);
    const sorted_nums = (await readline()).split(" ").map(Number);

    const n = nums.length;
    const map = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        const num = sorted_nums[i];
        map[num] = Math.floor(i / 3);
    }

    let queue = [];
    const blocks = {};

    nums.map((num) => map[num]).forEach((num) => {
        if (!queue.length || queue[queue.length - 1].num !== num) {
            queue.push({ num, count: 1 });
            if (!blocks[num]) blocks[num] = [];
            blocks[num].push(queue[queue.length - 1]);
        } else {
            queue[queue.length - 1].count++;
        }
    });

    let moved_count = 0;
    while (queue.length > 0) {
        const first = queue.shift();
        if (first.count === 0 || first.count === 3) continue;

        if (!queue.length) break;

        let second = queue[0];
        while (second.count === 0) {
            queue.shift();
            second = queue[0];
        }

        if (first.num === second.num) {
            second.count += first.count;
            continue;
        }

        if (first.count === 2) {
            moved_count += 1;
            blocks[first.num].forEach((block) => (block.count = 0));
            continue;
        }

        if (first.count === 1) {
            if (blocks[first.num].length === 3) {
                moved_count += 2;
                blocks[first.num].forEach((block) => (block.count = 0));
            } else {
                moved_count += 1;
                blocks[first.num].forEach((block) => (block.count = 3));
            }
        }
    }

    console.log(moved_count);
})();

Java算法源码

import java.util.*;

public class Main {
    static class NumCount {
        int num;
        int count;

        public NumCount(int num, int count) {
            this.num = num;
            this.count = count;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int n = nums.length;

        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int num = sc.nextInt();
            map.put(num, i / 3);
        }

        nums = Arrays.stream(nums).map(num -> map.get(num)).toArray();

        Map<Integer, LinkedList<NumCount>> blocks = new HashMap<>();
        LinkedList<NumCount> queue = new LinkedList<>();
        for (int num : nums) {
            if (queue.isEmpty() || queue.getLast().num != num) {
                queue.addLast(new NumCount(num, 1));
                blocks.putIfAbsent(num, new LinkedList<>());
                blocks.get(num).add(queue.getLast());
            } else {
                queue.getLast().count++;
            }
        }

        int moved_count = 0;

        while (!queue.isEmpty()) {