华为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真实机试环境,非其他第三方平台模拟。
输入描述
第一行输入初始排队顺序序列
第二行输入分组排队顺序序列
输出描述
最少调整多少次数
用例
题目解析
- 首先将输入的初始排队顺序序列和分组排队顺序序列转换为列表,例如输入为"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]。
- 初始化一个变量count用于记录调整次数。
- 遍历分组排队顺序列表,对于每个小组,检查初始排队顺序中对应的三个学生是否已经满足要求(即同组学生之间没有顺序要求),如果不满足,则进行以下操作: a. 找到当前小组在初始排队顺序中的起始位置start_index。 b. 计算当前小组在初始排队顺序中的结束位置end_index。 c. 将当前小组的学生按照分组排队顺序重新排列。 d. 将重新排列后的学生插入到初始排队顺序的start_index位置,并将原来start_index位置及其之后的学生向后移动。 e. 更新count的值。
- 最后输出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()) {
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
2024华为OD机试题库D卷 文章被收录于专栏
2024年5-11月份考的D卷,不用再看AB卷,CD卷题目一样。多种语言解法,欢迎提供更好的解法。