华为OD机试 - 小朋友分组最少调整次数 - 贪心算法（Python/JS/C/C++ 2024 E卷 100分）
华为OD机试 2024E卷题库疯狂收录中，刷题点这里
专栏导读
本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
一、题目描述
n (3 ≤ n ≤ 90000 且可以整除 3) 个学生排成一排，学生编号分别是 1 到 n，n 为 3 的整数倍数，老师随机抽签决定将所有学生分成 m 个 3 人的小组（n = 3 * m）。
为了便于同组学生交流，老师决定将小组成员安排到一起，也就是同组成员彼此相连，同组任意两个成员之间无其它组的成员。
因此老师决定调整队伍，老师每次可以调整任意一名学生到队伍的任意位置，计为调整了一次，请计算最少调整多少次可以达到目标。
注意：对于小组之间没有顺序要求，同组学生之间没有顺序要求。
二、输入描述
第一行输入初始排列顺序序列
第二行输入分组排列顺序序列
三、输出描述
输出一个整数k，表示至少调整k次。
四、测试用例
测试用例1：
1、输入
4 2 8 5 3 6 1 9 7
6 3 1 2 4 8 7 9 5
2、输出
1
3、说明
只有一个组（例如 [4, 2, 8] 对应的组号）需要调整位置，使其成员在最终排列中相邻。这意味着只需要一次调整就能实现目标排列。因此，输出结果为 1，表示至少需要一次调整。
测试用例2：
1、输入
8 9 7 5 6 3 2 1 4
7 8 9 4 2 1 3 5 6
2、输出
0
3、说明
每组3个学生的编号在初始排列和目标排列中的组号顺序已经是对应的，并且组内成员在初始排列中已经彼此相邻。
通过检查可以发现，每个组的成员在初始排列中已经满足相邻的条件，因此不需要进行任何调整。
五、解题思路
这道题的目的是通过最少的调整次数，将一组学生按照指定的目标顺序排列，使得同组的学生在最终排列中彼此相连。题目的核心在于寻找一种策略，能够有效地将学生移动到合适的位置，同时最小化移动次数。
在计算调整次数时，采用了一种贪心的策略，优先处理需要最少调整的情况（如两两交换），从而减少整体调整次数。
（1）将学生编号映射为组号：
我们的目标是将学生编号转化为组号。因为每个组有3个学生，我们可以通过将目标排列中的每个学生编号映射到其组号（即编号除以3）来得到初始序列中每个学生的目标组号。
（2）记录组号的位置：
我们需要记录每个组号在初始排列中的位置。为此，我们创建一个数组列表，每个列表存储对应组号在初始排列中出现的位置。
（3）计算最少调整次数：
我们通过遍历每个组的位置列表来计算是否需要调整。如果一个组的所有成员在初始序列中已经连续排列，那么不需要调整；否则，需要进行一次调整。
如果一个组只有一个成员，则需要两次调整，因为要将其与另两个成员排在一起。如果有两个成员且它们间隔较大，也需要一次调整。
（4）计算组间交错：
为了避免多余的调整，计算组间的交错情况。如果一个组的成员之间有其他组的成员插入，这表明需要额外的调整。通过遍历整个组号序列，记录每个组号的出现次数，我们可以发现是否存在组间交错，并调整次数。
（5）输出最小调整次数：
最后，我们取前述计算出的两种调整方法的最小值作为最终的最小调整次数。
六、Python算法源码
# 导入必要的模块
import sys
def main():
# 读取输入的初始排列顺序
initial_order = list(map(int, sys.stdin.readline().strip().split()))
# 读取输入的目标排列顺序
target_order = list(map(int, sys.stdin.readline().strip().split()))
student_count = len(initial_order)
group_count = student_count // 3
# 创建一个映射数组，将学生编号映射到目标序列中的组号
group_mapping = [0] * (student_count + 1)
for i in range(student_count):
group_mapping[target_order[i]] = i // 3
# 将初始顺序转换为组号数组
group_order = [group_mapping[student] for student in initial_order]
# 创建一个列表数组，用于存储每个组号在初始序列中出现的位置
group_positions = [[] for _ in range(group_count)]
for i, group in enumerate(group_order):
group_positions[group].append(i)
minimum_moves = 0
# 遍历每个组的位置列表，计算需要的最少移动次数
for positions in group_positions:
if len(positions) == 3:
# 如果一个组有3个成员，检查他们是否连续
if positions[1] - positions[0] > 1 or positions[2] - positions[1] > 1:
minimum_moves += 1
elif len(positions) == 2:
# 如果一个组有2个成员，检查他们是否间隔过大
if positions[1] - positions[0] > 2:
minimum_moves += 1
elif len(positions) == 1:
# 如果一个组只有1个成员，最坏情况需要两次调整
minimum_moves += 2
# 通过计算组间的交错情况，可能减少调整次数
encountered_groups = set()
overlap_adjustments = 0
for group in group_order:
if group not in encountered_groups:
encountered_groups.add(group)
else:
overlap_adjustments += 1
# 取两种调整方法的最小值
minimum_moves = min(minimum_moves, overlap_adjustments)
# 输出最小调整次数
print(minimum_moves)
# 调用主函数
if __name__ == "__main__":
main()
七、JavaScript算法源码
// 使用Node.js的readline模块读取输入
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
let inputLines = [];
rl.on('line', (line) => {
inputLines.push(line.trim());
if (inputLines.length === 2) {
rl.close();
}
});
rl.on('close', () => {
// 读取初始排列顺序
const initialOrder = inputLines[0].split(' ').map(Number);
// 读取目标排列顺序
const targetOrder = inputLines[1].split(' ').map(Number);
const studentCount = initialOrder.length;
const groupCount = studentCount / 3;
// 创建一个映射数组，将学生编号映射到目标序列中的组号
const groupMapping = new Array(studentCount + 1).fill(0);
for (let i = 0; i < studentCount; i++) {
groupMapping[targetOrder[i]] = Math.floor(i / 3);
}
// 将初始顺序转换为组号数组
const groupOrder = initialOrder.map(student => groupMapping[student]);
// 创建一个数组列表的数组，用于存储每个组号在初始序列中出现的位置
const groupPositions = Array.from({length: groupCount}, () => []);
for (let i = 0; i < groupOrder.length; i++) {
groupPositions[groupOrder[i]].push(i);
}
let minimumMoves = 0;
// 遍历每个组的位置列表，计算需要的最少移动次数
for (const positions of groupPositions) {
if (positions.length === 3) {
// 如果一个组有3个成员，检查他们是否连续
if (positions[1] - positions[0] > 1 || positions[2] - positions[1] > 1) {
minimumMoves++;
}
} else if (positions.length === 2) {
// 如果一个组有2个成员，检查他们是否间隔过大
if (positions[1] - positions[0] > 2) {
minimumMoves++;
}
} else if (positions.length === 1) {
// 如果一个组只有1个成员，最坏情况需要两次调整
minimumMoves += 2;
}
}
// 通过计算组间的交错情况，可能减少调整次数
const encounteredGroups = new Set();
let overlapAdjustments = 0;
for (const group of groupOrder) {
if (!encounteredGroups.has(group)) {
encounteredGroups.add(group);
} else {
overlapAdjustments++;
}
}
// 取两种调整方法的最小值
minimumMoves = Math.min(minimumMoves, overlapAdjustments);
// 输出最小调整次数
console.log(minimumMoves);
});
八、C算法源码
#include <stdio.h>
#include <stdlib.h>
// 主函数
int main() {
// 定义变量
int n = 0;
int initialOrder[90000];
int targetOrder[90000];
// 读取初始排列顺序
while (scanf("%d", &initialOrder[n]) != EOF && getchar() != '\n') {
n++;
}
// 读取目标排列顺序
int m = 0;
while (scanf("%d", &targetOrder[m]) != EOF && getchar() != '\n') {
m++;
}
// 计算组数
int groupCount = n / 3;
// 创建组映射数组，将学生编号映射到组号
int *groupMapping = (int *)malloc((n + 1) * sizeof(int));
for (int i = 0; i < m; i++) {
groupMapping[targetOrder[i]] = i / 3;
}
// 将初始顺序转换为组号数组
int groupOrder[90000];
for (int i = 0; i < n; i++) {
groupOrder[i] = groupMapping[initialOrder[i]];
}
// 创建组位置数组
int **groupPositions = (int **)malloc(groupCount * sizeof(int *));
int *counts = (int *)calloc(groupCount, sizeof(int));
for (int i = 0; i < groupCount; i++) {
groupPositions[i] = (int *)malloc(3 * sizeof(int));
}
// 记录每个组的位置
for (int i = 0; i < n; i++) {
int group = groupOrder[i];
groupPositions[group][counts[group]++] = i;
}
int minimumMoves = 0;
// 遍历每个组，计算调整次数
for (int i = 0; i < groupCount; i++) {
if (counts[i] == 3) {
if (groupPositions[i][1] - groupPositions[i][0] > 1 || groupPositions[i][2] - groupPositions[i][1] > 1) {
minimumMoves++;
}
} else if (counts[i] == 2) {
if (groupPositions[i][1] - groupPositions[i][0] > 2) {
minimumMoves++;
}
} else if (counts[i] == 1) {
minimumMoves += 2;
}
}
// 计算组间的交错情况
int *encounteredGroups = (int *)calloc(groupCount, sizeof(int));
int overlapAdjustments = 0;
for (int i = 0; i < n; i++) {
int group = groupOrder[i];
if (!encounteredGroups[group]) {
encounteredGroups[group] = 1;
} else {
overlapAdjustments++;
}
}
// 取最小调整次数
if (overlapAdjustments < minimumMoves) {
minimumMoves = overlapAdjustments;
}
// 输出结果
printf("%d\n", minimumMoves);
// 释放内存
free(groupMapping);
for (int i = 0; i < groupCount; i++) {
free(groupPositions[i]);
}
free(groupPositions);
free(counts);
free(encounteredGroups);
return 0;
}
九、C++算法源码
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
// 读取初始排列顺序
vector<int> initialOrder;
string line;
getline(cin, line);
stringstream ss(line);
int num;
while(ss >> num){
initialOrder.push_back(num);
}
// 读取目标排列顺序
vector<int> targetOrder;
getline(cin, line);
stringstream ss2(line);
while(ss2 >> num){
targetOrder.push_back(num);
}
int n = initialOrder.size();
int groupCount = n / 3;
// 创建组映射数组，将学生编号映射到组号
vector<int> groupMapping(n+1, 0);
for(int i=0;i<n;i++){
groupMapping[targetOrder[i]] = i / 3;
}
// 将初始顺序转换为组号数组
vector<int> groupOrder(n, 0);
for(int i=0;i<n;i++){
groupOrder[i] = groupMapping[initialOrder[i]];
}
// 创建组位置数组
vector<vector<int>> groupPositions(groupCount, vector<int>());
for(int i=0;i<n;i++){
groupPositions[groupOrder[i]].push_back(i);
}
int minimumMoves = 0;
// 遍历每个组，计算调整次数
for(auto &positions : groupPositions){
if(positions.size() == 3){
if(positions[1] - positions[0] > 1 || positions[2] - positions[1] > 1){
minimumMoves++;
}
}
else if(positions.size() == 2){
if(positions[1] - positions[0] > 2){
minimumMoves++;
}
}
else if(positions.size() == 1){
minimumMoves += 2;
}
}
// 计算组间的交错情况
unordered_set<int> encounteredGroups;
int overlapAdjustments = 0;
for(auto &group : groupOrder){
if(encounteredGroups.find(group) == encounteredGroups.end()){
encounteredGroups.insert(group);
}
else{
overlapAdjustments++;
}
}
// 取最小调整次数
minimumMoves = min(minimumMoves, overlapAdjustments);
// 输出结果
cout << minimumMoves;
return 0;
}
🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）
🏆本文收录于，华为OD机试真题（Python/JS/C/C++）
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
