小朋友分组最少调整次数

题目描述

n(3≤n≤90000 且可以整除 3)个学生排成一排，学生编号分别是1到n,n为3的整数倍数，老师随机抽签决定将所有学生分成 m 个3人的小组(n=3*m)。
为了便于同组学生交流，老师决定将小组成员安排到一起，也就是同组成员彼此相连，同组任意两个成员之间无其它组的成员。
因此老师决定调整队伍，老师每次可以调整任意一名学生到队伍的任意位置，计为调整了一次，请计算最少调整多少次可以达到目标。

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

输入描述

第一行输入初始排列顺序序列
第二行输入分组排列顺序序列

输出描述

输出一个整数k，表示至少调整k次。

/*
4 2 8 5 3 6 1 9 7
6 3 1 2 4 8 7 9 5
18 9 7 5 6 3 2 1 4
7 8 9 4 2 1 3 5 6
07 12 9 4 8 1 3 2 6 10 5 11
7 8 9 4 2 1 3 5 6 10 12 11
34 3 7 8 2 1 9 5 6
7 8 9 4 2 1 3 5 6
2*/
public class 小朋友分组最少调整次数 {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 获取控制台输入信息int[] initialOrder = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();int[] targetOrder = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();int studentCount = initialOrder.length;// 创建一个映射数组，用于将学生编号映射到目标序列中的组号int[] groupMapping = new int[studentCount+1];for (int i = 0; i < studentCount; i++) {groupMapping[targetOrder[i]] = i / 3;}// 将初始顺序转换为组号数组int[] groupOrder = Arrays.stream(initialOrder).map(student -> groupMapping[student]).toArray();// 存储所有的分组标识TreeSet<Integer> allgroup = new TreeSet<>();for (int i : groupMapping) {allgroup.add(i);}// 标记那些分组标识已经被使用TreeSet<Integer> uesdGroup = new TreeSet<>();// 用于存储当前组和目标组不同的信息ArrayList<Node> nodes = new ArrayList<>();// 寻找当前组和目标组不同的小朋友for (int i = 0; i < groupOrder.length; i += 3) {int i0 = groupOrder[i];int i1 = groupOrder[i + 1];int i2 = groupOrder[i + 2];if (i0 == i1 && i1 == i2){uesdGroup.add(i0);continue;}else if (i0 != i1 && i1 != i2 && i0 != i2){int g = i0;if (!uesdGroup.contains(i1)){g = i1;}else if (!uesdGroup.contains(i2)){g = i2;}nodes.add(new Node(g,i0,i));nodes.add(new Node(g,i2,i+2));nodes.add(new Node(g,i1,i+1));uesdGroup.add(g);}else {int tempGroup = i0;if (i0 == i1 && i1 != i2){tempGroup = i0;nodes.add(new Node(i0,i2,i+2));}else if (i0 != i1 && i1 == i2){tempGroup = i1;nodes.add(new Node(i1,i0,i));}else if (i0 == i2 && i1 != i2){tempGroup = i1;nodes.add(new Node(i0,i1,i+1));}// 处理三个小朋友的组标识不同时，随意取的任意组标识冲突问题if (uesdGroup.contains(tempGroup)){ArrayList<Integer> unUsedG = new ArrayList<>();for (int g = 0; g < allgroup.size(); g++) {if (!uesdGroup.contains(g)){unUsedG.add(g);}}for (int j = 0; j < nodes.size(); j++) {Node node = nodes.get(j);Node node1 = nodes.get(j+1);Node node2 = nodes.get(j+2);if (node.curGroup == tempGroup && node.index/3 == node1.index/3 && node1.index/3 == node2.index/3 ){node.curGroup = unUsedG.get(0);node1.curGroup = unUsedG.get(0);node2.curGroup = unUsedG.get(0);break;}}}else {uesdGroup.add(tempGroup);}}}// 移动位置，使其能够正确分组int minimumMoves = 0;for (int i = 0; i < nodes.size(); i++) {Node node = nodes.get(i);if (node.curGroup != node.targetGroup){for (int j = i+1; j < nodes.size(); j++) {Node node1 = nodes.get(j);if (node.targetGroup == node1.curGroup && node.index/3 != node1.index/3){node1.curGroup = node.curGroup;node.curGroup = node.targetGroup;minimumMoves++;break;}}}}// 输出最小调整次数System.out.println(minimumMoves);}static class Node {int curGroup;int targetGroup;int index;public Node(int curGroup, int targetGroup, int index) {this.curGroup = curGroup;this.targetGroup = targetGroup;this.index = index;}}
}