学生重新排队【华为OD机试JAVA&Python&C++&JS题解】

标签：index JAVA cur int 题解 OD relations student order

一. 题目-学生重新排队

n个学生排成一排，学生编号分别是1到n，n为3的整倍数。老师随机抽签决定将所有学生分成m个3人的小组，n=3*m
为了便于同组学生交流，老师决定将小组成员安排到一起，也就是同组成员彼此相连，同组任意两个成员输入描述：之间无其它组的成员。
因此老师决定调整队伍，老师每次可以调整任何一名学生到队伍的任意位置，计为调整了一次，
请计算最少调整多少次可以达到目标。
注意：对于小组之间没有顺序要求，同组学生之间没有顺序要求。
两行字符串，空格分隔表示不同的学生编号
第一行是学生目前排队情况
第二行是随机抽签分组情况，从左开始每3个元素为一组
n 为学生的数量， n的范围为[3, 900], n一定为3的整倍数
第一行和第二行的元素个数一定相同
输出描述：

老师调整学生达到同组彼此相连的最小次数

补充说明：

同组相连：同组任意两个成员之间无其它组的成员，比如有两个小组[4 5 6] [1 2 3],以下结果都满足要求

1 2 3 4 5 6

1 3 2 4 5 6

2 3 1 5 6 4

5 6 4 1 2 3

以下结果不满足要求

1 2 4 3 5 6， 4与5之间存在其它组的成员3

示例1

输入：

7 9 8 5 6 4 2 1 3
7 8 9 4 2 1 3 5 6
输出：

1
说明：

学生目前排队情况: 7 9 8 5 6 4 2 1 3
学生分组情况：[7 8 9] [4 2 1] [3 5 6]
将3调整到4之前，队列调整为 7 9 8 5 6 3 4 2 1，那么三个小组成员均彼此相连[7 9 8] [5 6 3] [4 2 1]
输出：1
示例2

输入：

8 9 7 5 6 3 2 1 4
7 8 9 4 2 1 3 5 6
输出：

0
说明：

学生目前排队情况: 7 9 8 5 6 3 2 1 4
学生分组情况：[7 8 9] [4 2 1] [3 5 6]
无需调整，三个小组成员均彼此相连[7 9 8] [5 6 3] [2 1 4]
输出：0

二.解题思路

建立索引字典： 将学生目前排队情况转换成索引字典，其中键为学生编号，值为该学生在队伍中的索引位置。
遍历每个小组： 对于每个小组，遍历其中的学生。
计算目标位置： 对于每个小组的学生，计算其目标位置。目标位置是该学生在小组中的相对位置乘以3再加上该小组在整个队伍中的位置。
调整位置： 如果当前位置不是目标位置，则需要进行调整。通过交换当前位置和目标位置的学生，使得小组内的学生在队伍中是连续排列。
更新索引字典： 调整后更新索引字典，确保索引字典中的信息是最新的。
累计调整次数： 统计每次调整，最终得到最少调整次数。

通过以上步骤，可以确保同组成员在队伍中是彼此相连的。在代码中，需要注意索引的计算以及列表中的元素交换。这个思路的关键在于通过交换操作，逐步调整队伍中学生的位置，使得每个小组的学生都连续排列。

三.题解代码

Python题解代码

import functools
import sys
from collections import Counter, defaultdict
import copy
from itertools import permutations
import re
import math
import sys
import queue

cur_order = [int(x) for x in input().split(" ")]
final_order = [int(x) for x in input().split(" ")]
order_flags = [0 for x in range(len(cur_order))]
n = len(cur_order)
# map<学生编号, 组号>
relations = {}
result = 0


# 判断每一位同学是否都在对应组内
def check_order():
    global cur_order, final_order, order_flags, n, relations, result
    i = 0
    while (True):
        if (i >= n):
            break
        else:
            if (not (relations[cur_order[i]] == relations[cur_order[i + 1]] and
                     relations[cur_order[i]] == relations[cur_order[i + 2]])):
                return False
        i += 3
    return True


def move(cur_student, remove_index, append_index):
    global cur_order, final_order, order_flags, n, relations, result
    if (relations[cur_order[remove_index]] == relations[cur_student]):
        remove_element = cur_order[remove_index]
        cur_order.pop(remove_index)
        cur_order.insert(append_index, remove_element)


def two_step_move():
    global cur_order, final_order, order_flags, n, relations, result
    for i in range(n):
        cur_student = cur_order[i]
        if (order_flags[relations[cur_student]] == 0):
            result += 2
            for j in range(n):
                if (cur_order[j] != cur_student):
                    move(cur_student, j, i)


# 以当前学生为准，判断他后面的两个学生是否与其同组
def get_cur_order_cnt(index, cur_student):
    global cur_order, final_order, order_flags, n, relations, result
    count = 0
    cur_stu_order = relations[cur_student]
    if (index + 1 < n and relations[cur_order[index + 1]] == cur_stu_order):
        order_flags[relations[cur_student]] = 1
        count += 1
        if (index + 2 < n and relations[cur_order[index + 2]] == cur_stu_order):
            count += 1
    return count


k = 0
while (True):
    if (k >= n):
        break
    else:
        for j in range(3):
            relations[final_order[k + j]] = k // 3 + 1
    k += 3

while (not check_order()):
    operation_flag = 0
    i = 0
    while (True):
        if (i >= n):
            break
        else:
            cur_student = cur_order[i]
            if (order_flags[relations[cur_student]] == 0):
                # 后面有一个学生与其同组，那么需要操作1次
                # 后面有两个学生与其同组，那么需要操作0次,无需操作
                if (get_cur_order_cnt(i, relations[cur_student]) == 1):
                    result += 1
                    operation_flag = 1
                    for j in range(n):
                        if (j != i and j != i + 1):
                            move(cur_student, j, i)
        i += 1
    # 若每一个学生后面两个学生都没有与其同组的情况
    # 需要操作2次，将其后面两位都移动,然后再循环的去遍历,判读是否满足分组情况
    if (operation_flag == 0):
        two_step_move()

print(result)

JAVA题解代码

import java.util.Scanner;
import java.util.*;
import java.util.stream.Stream;
import java.util.HashMap;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.stream.Collectors;
 
 
 
 
public class Main {
    public static List<Integer> cur_order = new ArrayList<>();
    public static List<Integer> final_order= new ArrayList<>();
    public static List<Integer> order_flags= new ArrayList<>();
    public static int n=0;
    //map<学生编号, 组号>
    public static Map<Integer, Integer> relations=new HashMap<>(); 
    public static int result = 0;
    
    //判断每一位同学是否都在对应组内
    public static boolean check_order(){
        for (int i = 0; i < cur_order.size(); i += 3) {
            if (!(relations.get(cur_order.get(i)) == relations.get(cur_order.get(i + 1)) && 
                relations.get(cur_order.get(i)) == relations.get(cur_order.get(i + 2)))){
                return false;
            }
        }
        return true;
    }
    
    public static void move(int cur_student, int remove_index, int append_index){
        if (relations.get(cur_order.get(remove_index)) == relations.get(cur_student)) {
            int remove_element = cur_order.get(remove_index);
            cur_order.remove(remove_index);
            cur_order.add(append_index, remove_element);
        }
    }
    
    public static void two_step_move(){
        for (int i = 0; i < n; i++) {
            int cur_student = cur_order.get(i);
            if (order_flags.get(relations.get(cur_student))==0) {
                result += 2;
                for (int j = 0; j < n; j++) {
                    if (cur_order.get(j) != cur_student) {
                        move(cur_student,j,i);
                    }
                }
            }
        }
    }
    
    //以当前学生为准，判断他后面的两个学生是否与其同组
    public static int get_cur_order_cnt(int index, int cur_student){
        int count = 0; 
        int cur_stu_order = relations.get(cur_student);
        if (index + 1 < n && relations.get(cur_order.get(index + 1)) == cur_stu_order) {
            order_flags.set(relations.get(cur_student), 1);
            count+=1;
            if(index + 2 < n && relations.get(cur_order.get(index + 2)) == cur_stu_order){
                count+=1;
            }
        }
        return count;
    }
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] tmp1 = in.nextLine().split(" ");
        for (int i = 0; i < tmp1.length; i++) {  
            cur_order.add(Integer.parseInt(tmp1[i]));
        }
        String[] tmp2 = in.nextLine().split(" ");
        for (int i = 0; i < tmp2.length; i++) {  
            final_order.add(Integer.parseInt(tmp2[i]));
        }
        n = cur_order.size();
        for (int j = 0; j < n; j++) {
            order_flags.add(0);
        }
        
        int k=0;
        while(true){
            if(k>=n){
                break;
            } else {
                for (int j = 0; j < 3; j++) {
                    relations.put((final_order.get(k + j)) , k / 3 + 1);
                }
            }
            k+=3;
        }
    
     
        while (!check_order()) {
            int operation_flag = 0;  
    
            int i=0;
            while(true){
                if(i>=n){
                    break;
                } else {
                    int cur_student = cur_order.get(i);
                    if (order_flags.get(relations.get(cur_student))==0){
                        //后面有一个学生与其同组，那么需要操作1次
                        //后面有两个学生与其同组，那么需要操作0次,无需操作
                        if (get_cur_order_cnt(i, relations.get(cur_student)) == 1) {
                            result += 1;
                            operation_flag = 1; 
                            for (int j = 0; j < n; j++) {
                                if (j != i && j != i + 1) {
                                    move(cur_student,j,i);
                                }
                            }
                        }
                    } 
     
                }
                i+=1;
            }
    
            // 若每一个学生后面两个学生都没有与其同组的情况
            // 需要操作2次，将其后面两位都移动,然后再循环的去遍历,判读是否满足分组情况
            if (operation_flag==0) {
                two_step_move();
            }
        }
        System.out.println(result);
    }
 
    public static int[] split(String input_str){
        String[] tmp2 = input_str.split(",");
        int[] nums = new int[tmp2.length];
        for (int i = 0; i < tmp2.length; i++) {  
            nums[i] = Integer.parseInt(tmp2[i]);
        }
        return nums;
    }
 
 
}

C/C++题解代码

#include<iostream>
#include<vector>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
#include<exception> 
#include<map>
#include<cmath>
#include<unordered_map>
#include<numeric>
#include<set>
#include<climits>
#include<ctype.h>
#include<queue>
#include<stack>
#include<list>
#include<bitset>
#include <regex>
using namespace std;
 
vector<int> split(string params_str) {
    vector<int> p;
    while (params_str.find(" ") != string::npos) {
        int found = params_str.find(" ");
        p.push_back(stoi(params_str.substr(0, found)));
        params_str = params_str.substr(found + 1);
    }    
    p.push_back(stoi(params_str));
    return p;
}
 
vector<string> split_str(string params_str) {
    vector<string> p;
    while (params_str.find(",") != string::npos) {
        int found = params_str.find(",");
        p.push_back(params_str.substr(0, found));
        params_str = params_str.substr(found + 1);
    }    
    p.push_back(params_str);
    return p;
}  
 
vector<int> cur_order;
vector<int> final_order;
vector<int> order_flags;
int n;
//map<学生编号, 组号>
map<int, int> relations; 
int result = 0;
 
//判断每一位同学是否都在对应组内
bool check_order(){
    for (int i = 0; i < cur_order.size(); i += 3) {
        if (!(relations[cur_order[i]] == relations[cur_order[i + 1]] && 
            relations[cur_order[i]] == relations[cur_order[i + 2]])){
            return false;
        }
    }
    return true;
}
 
void move(int cur_student, int remove_index, int append_index){
    if (relations[cur_order[remove_index]] == relations[cur_student]) {
        int remove_element = cur_order[remove_index];
        cur_order.erase(cur_order.begin() + remove_index);
        cur_order.insert(cur_order.begin() + append_index, remove_element);
    }
}
 
void two_step_move(){
    for (int i = 0; i < n; i++) {
        int cur_student = cur_order[i];
        if (!order_flags[relations[cur_student]]) {
            result += 2;
            for (int j = 0; j < n; j++) {
                if (cur_order[j] != cur_student) {
                    move(cur_student,j,i);
                }
            }
        }
    }
}
 
//以当前学生为准，判断他后面的两个学生是否与其同组
int get_cur_order_cnt(int index, int cur_student){
    int count = 0; 
    int cur_stu_order = relations[cur_student];
    if (index + 1 < n && relations[cur_order[index + 1]] == cur_stu_order) {
        order_flags[relations[cur_student]] = true;
        count+=1;
        if(index + 2 < n && relations[cur_order[index + 2]] == cur_stu_order){
            count+=1;
        }
    }
    return count;
}
 
int main()
{
    string input_str1,input_str2;
    getline(cin, input_str1);
    getline(cin, input_str2);
    cur_order = split(input_str1);
    final_order = split(input_str2);
    //当前学生编号是否满足分组情况
    n = cur_order.size();
    for (int j = 0; j < n; j++) {
        order_flags.push_back(0);
    }
    
    int k=0;
    while(true){
        if(k>=n){
            break;
        } else {
            for (int j = 0; j < 3; j++) {
                relations[final_order[k + j]] = k / 3 + 1;
            }
        }
        k+=3;
    }
 
 
    while (!check_order()) {
        int operation_flag = 0;  
 
        int i=0;
        while(true){
            if(i>=n){
                break;
            } else {
                int cur_student = cur_order[i];
                if (order_flags[relations[cur_student]]==0){
                    //后面有一个学生与其同组，那么需要操作1次
                    //后面有两个学生与其同组，那么需要操作0次,无需操作
                    if (get_cur_order_cnt(i, relations[cur_student]) == 1) {
                        result += 1;
                        operation_flag = 1; 
                        for (int j = 0; j < n; j++) {
                            if (j != i && j != i + 1) {
                                move(cur_student,j,i);
                            }
                        }
                    }
                } 
 
            }
            i+=1;
        }
 
        // 若每一个学生后面两个学生都没有与其同组的情况
        // 需要操作2次，将其后面两位都移动,然后再循环的去遍历,判读是否满足分组情况
        if (operation_flag==0) {
            two_step_move();
        }
    }
    cout << result << endl;
 
    return 0;
}

JS题解代码

let cur_order=[];
let final_order=[];
let order_flags=[];
let n=0;
//map<学生编号, 组号>
let relations={}; 
let result = 0;
 
//判断每一位同学是否都在对应组内
function check_order(){
    for (let i = 0; i < cur_order.length; i += 3) {
        if (!(relations[cur_order[i]] == relations[cur_order[i + 1]] && 
            relations[cur_order[i]] == relations[cur_order[i + 2]])){
            return false;
        }
    }
    return true;
}
 
function move(cur_student, remove_index, append_index){
    if (relations[cur_order[remove_index]] == relations[cur_student]) {
        remove_element = cur_order[remove_index];
        cur_order.splice(remove_index,1);
        cur_order.splice(append_index,0, remove_element);
    }
}
 
function two_step_move(){
    for (let i = 0; i < n; i++) {
        cur_student = cur_order[i];
        if (!order_flags[relations[cur_student]]) {
            result += 2;
            for (let j = 0; j < n; j++) {
                if (cur_order[j] != cur_student) {
                    move(cur_student,j,i);
                }
            }
        }
    }
}
 
//以当前学生为准，判断他后面的两个学生是否与其同组
function get_cur_order_cnt(index, cur_student){
    count = 0; 
    cur_stu_order = relations[cur_student];
    if (index + 1 < n && relations[cur_order[index + 1]] == cur_stu_order) {
        order_flags[relations[cur_student]] = true;
        count+=1;
        if(index + 2 < n && relations[cur_order[index + 2]] == cur_stu_order){
            count+=1;
        }
    }
    return count;
}
 
 
 
function main(arr1, arr2) {
    cur_order = arr1
    final_order = arr2
    //当前学生编号是否满足分组情况
    n = cur_order.length;
    for (let j = 0; j < n; j++) {
        order_flags.push(0);
    }
    
    let k=0;
    while(true){
        if(k>=n){
            break;
        } else {
            for (let j = 0; j < 3; j++) {
                relations[final_order[k + j]] = k / 3 + 1;
            }
        }
        k+=3;
    }
 
 
    while (!check_order()) {
        let operation_flag = 0;  
        let i=0;
        while(true){
            if(i>=n){
                break;
            } else {
                let cur_student = cur_order[i];
                if (order_flags[relations[cur_student]]==0){
                    //后面有一个学生与其同组，那么需要操作1次
                    //后面有两个学生与其同组，那么需要操作0次,无需操作
                    if (get_cur_order_cnt(i, relations[cur_student]) == 1) {
                        result += 1;
                        operation_flag = 1; 
                        for (let j = 0; j < n; j++) {
                            if (j != i && j != i + 1) {
                                move(cur_student,j,i);
                            }
                        }
                    }
                } 
 
            }
            i+=1;
        }
 
        // 若每一个学生后面两个学生都没有与其同组的情况
        // 需要操作2次，将其后面两位都移动,然后再循环的去遍历,判读是否满足分组情况
        if (operation_flag==0) {
            two_step_move();
        }
    }
    console.log(result);
}
 
main([7, 9 ,8, 5, 6, 4, 2, 1, 3],
[7, 8 ,9 ,4 ,2, 1, 3 ,5, 6]
)

四.代码讲解(Java&Python&C++&JS分别讲解)

Python 题解代码解析：

转换为数字列表： 使用 list(map(int, current_line.split())) 和 list(map(int, target_line.split())) 将输入的字符串转换为数字列表，分别表示当前队伍和目标队伍的学生编号。
位置信息获取： 定义 get_positions 函数，该函数接受一个学生列表并返回一个字典，表示每个学生在队伍中的位置。
调整次数计算： 使用两个字典 current_positions 和 target_positions 分别保存当前队伍和目标队伍学生的位置。然后通过遍历每个学生，比较其在当前队伍中的位置和目标位置是否一致，若不一致则进行位置调整。
返回调整次数： 返回调整次数作为最终结果。

Java 题解代码解析：

输入解析： 使用 strToIntArray 函数将输入的字符串转换为整数数组，分别表示当前队伍和目标队伍的学生编号。
调整次数计算： 使用 minAdjustments 函数遍历每个小组，对于每个小组，使用 countAdjustments 函数计算该小组内学生的调整次数。在 countAdjustments 函数中，遍历小组内的学生，比较其在当前队伍中的位置和目标位置是否一致，若不一致则进行调整。
返回调整次数： 返回总的调整次数作为最终结果。

C/C++ 题解代码解析：

输入解析： 使用 istringstream 将输入的字符串转换为整数数组，分别表示当前队伍和目标队伍的学生编号。
调整次数计算： 使用两个循环分别遍历每个小组和小组内的学生，通过交换学生在当前队伍中的位置，实现位置调整。
返回调整次数： 返回调整次数作为最终结果。

JS 题解代码解析：

字符串转数组： 使用 split 函数将输入的字符串分割成数组，分别表示当前队伍和目标队伍的学生编号。
调整次数计算： 使用两个嵌套循环分别遍历每个小组和小组内的学生，通过交换学生在当前队伍中的位置，实现位置调整。
返回调整次数： 返回调整次数作为最终结果。

寄语

标签：index,JAVA,cur,int,题解,OD,relations,student,order
From： https://blog.csdn.net/mrdeam/article/details/137399956