题目链接

【华为OD机考 统一考试机试C卷】小朋友分组最少调整次数（C++ Java JavaScript Python C语言）

https://blog.csdn.net/banxia_frontend/article/details/136192490

java

import java.util.*;

public class Main {

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

        // 读取并解析初始的学生（序号）排队顺序
        int[] initialOrder = 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++) {
            int studentNumber = scanner.nextInt();  // 读取每个学生的序号
            groupMapping[studentNumber] = i / 3;  // 每三个学生分为一组，映射组号
        }

        // 创建一个链表用于合并相邻相同组号的学生
        LinkedList<int[]> groupQueue = new LinkedList<>();
        for (int studentNumber : initialOrder) {
            int groupId = groupMapping[studentNumber];  // 获取学生对应的组号

            if (groupQueue.isEmpty() || groupQueue.getLast()[0] != groupId) {
                // 如果队列为空或者最后一个组与当前学生组不同，新增一个组
                groupQueue.addLast(new int[]{groupId, 1});
            } else {
                // 如果最后一个组与当前学生组相同，则增加该组的学生数
                groupQueue.getLast()[1]++;
            }
        }

        // 记录需要调整的次数
        int adjustmentCount = 0;
        while (!groupQueue.isEmpty()) {
            int[] currentGroup = groupQueue.removeFirst();  // 取出第一个组

            if (currentGroup[1] == 1) {
                // 如果当前组只有一个学生
                int[] nextGroup = groupQueue.getFirst();  // 获取下一个组

                while (nextGroup[1] == 3) {
                    // 如果下一个组的学生数为3，继续获取下一个组
                    groupQueue.removeFirst();
                    nextGroup = groupQueue.getFirst();
                }

                if (nextGroup[0] == currentGroup[0] && nextGroup[1] == 2) {
                    // 如果下一个组与当前组组号相同且有两个学生，则需要一次调整
                    adjustmentCount++;
                    groupQueue.removeFirst();  // 移除下一个组
                } else {
                    // 否则需要两次调整
                    adjustmentCount += 2;

                    // 重新排列剩余的组
                    LinkedList<int[]> rearrangedQueue = new LinkedList<>();
                    while (!groupQueue.isEmpty()) {
                        int[] group = groupQueue.removeFirst();

                        if (group[0] == currentGroup[0]) {
                            continue;  // 跳过与当前组号相同的组
                        }

                        if (rearrangedQueue.isEmpty() || rearrangedQueue.getLast()[0] != group[0]) {
                            rearrangedQueue.addLast(new int[]{group[0], group[1]});
                        } else {
                            rearrangedQueue.getLast()[1] += group[1];
                        }
                    }
                    groupQueue = rearrangedQueue;  // 更新队列
                }
            } else if (currentGroup[1] == 2) {
                // 如果当前组有两个学生
                adjustmentCount += 1;

                // 重新排列剩余的组
                LinkedList<int[]> rearrangedQueue = new LinkedList<>();
                while (!groupQueue.isEmpty()) {
                    int[] group = groupQueue.removeFirst();

                    if (group[0] == currentGroup[0]) {
                        continue;  // 跳过与当前组号相同的组
                    }

                    if (rearrangedQueue.isEmpty() || rearrangedQueue.getLast()[0] != group[0]) {
                        rearrangedQueue.addLast(new int[]{group[0], group[1]});
                    } else {
                        rearrangedQueue.getLast()[1] += group[1];
                    }
                }
                groupQueue = rearrangedQueue;  // 更新队列
            }
        }

        System.out.println(adjustmentCount);  // 输出调整次数
    }
}

python

import sys
from collections import deque

# 读取输入
input = sys.stdin.read
data = input().split()

# 初始排队顺序
initial_order = list(map(int, data[:data.index("")]))
# 分组排队顺序
group_order = list(map(int, data[data.index("") + 1:]))

# 学生总数
student_count = len(initial_order)

# 创建序号到组号的映射关系数组
group_mapping = [0] * (student_count + 1)
for i in range(student_count):
   student_number = group_order[i]  # 读取每个学生的序号
   group_mapping[student_number] = i // 3  # 每三个学生分为一组，映射组号

# 创建一个链表用于合并相邻相同组号的学生
group_queue = deque()
for student_number in initial_order:
   group_id = group_mapping[student_number]  # 获取学生对应的组号

   if not group_queue or group_queue[-1][0] != group_id:
       # 如果队列为空或者最后一个组与当前学生组不同，新增一个组
       group_queue.append([group_id, 1])
   else:
       # 如果最后一个组与当前学生组相同，则增加该组的学生数
       group_queue[-1][1] += 1

# 记录需要调整的次数
adjustment_count = 0
while group_queue:
   current_group = group_queue.popleft()  # 取出第一个组

   if current_group[1] == 1:
       # 如果当前组只有一个学生
       next_group = group_queue[0]  # 获取下一个组

       while next_group[1] == 3:
           # 如果下一个组的学生数为3，继续获取下一个组
           group_queue.popleft()
           next_group = group_queue[0]

       if next_group[0] == current_group[0] and next_group[1] == 2:
           # 如果下一个组与当前组组号相同且有两个学生，则需要一次调整
           adjustment_count += 1
           group_queue.popleft()  # 移除下一个组
       else:
           # 否则需要两次调整
           adjustment_count += 2

           # 重新排列剩余的组
           rearranged_queue = deque()
           while group_queue:
               group = group_queue.popleft()

               if group[0] == current_group[0]:
                   continue  # 跳过与当前组号相同的组

               if not rearranged_queue or rearranged_queue[-1][0] != group[0]:
                   rearranged_queue.append([group[0], group[1]])
               else:
                   rearranged_queue[-1][1] += group[1]
           group_queue = rearranged_queue  # 更新队列
   elif current_group[1] == 2:
       # 如果当前组有两个学生
       adjustment_count += 1

       # 重新排列剩余的组
       rearranged_queue = deque()
       while group_queue:
           group = group_queue.popleft()

           if group[0] == current_group[0]:
               continue  # 跳过与当前组号相同的组

           if not rearranged_queue or rearranged_queue[-1][0] != group[0]:
               rearranged_queue.append([group[0], group[1]])
           else:
               rearranged_queue[-1][1] += group[1]
       group_queue = rearranged_queue  # 更新队列

print(adjustment_count)  # 输出调整次数

javascript

const readline = require('readline');

// 创建接口以读取标准输入
const rl = readline.createInterface({
   input: process.stdin,
   output: process.stdout
});

// 读取输入数据
let inputLines = [];
rl.on('line', (line) => {
   inputLines.push(line);
   if (inputLines.length === 2) {
       rl.close();
   }
});

rl.on('close', () => {
   // 初始排队顺序
   let initialOrder = inputLines[0].split(' ').map(Number);
   // 分组排队顺序
   let groupOrder = inputLines[1].split(' ').map(Number);

   // 学生总数
   let studentCount = initialOrder.length;

   // 创建序号到组号的映射关系数组
   let groupMapping = new Array(studentCount + 1).fill(0);
   for (let i = 0; i < studentCount; i++) {
       let studentNumber = groupOrder[i];  // 读取每个学生的序号
       groupMapping[studentNumber] = Math.floor(i / 3);  // 每三个学生分为一组，映射组号
   }

   // 创建一个队列用于合并相邻相同组号的学生
   let groupQueue = [];
   for (let studentNumber of initialOrder) {
       let groupId = groupMapping[studentNumber];  // 获取学生对应的组号

       if (groupQueue.length === 0 || groupQueue[groupQueue.length - 1][0] !== groupId) {
           // 如果队列为空或者最后一个组与当前学生组不同，新增一个组
           groupQueue.push([groupId, 1]);
       } else {
           // 如果最后一个组与当前学生组相同，则增加该组的学生数
           groupQueue[groupQueue.length - 1][1]++;
       }
   }

   // 记录需要调整的次数
   let adjustmentCount = 0;
   while (groupQueue.length > 0) {
       let currentGroup = groupQueue.shift();  // 取出第一个组

       if (currentGroup[1] === 1) {
           // 如果当前组只有一个学生
           let nextGroup = groupQueue[0];  // 获取下一个组

           while (nextGroup[1] === 3) {
               // 如果下一个组的学生数为3，继续获取下一个组
               groupQueue.shift();
               nextGroup = groupQueue[0];
           }

           if (nextGroup[0] === currentGroup[0] && nextGroup[1] === 2) {
               // 如果下一个组与当前组组号相同且有两个学生，则需要一次调整
               adjustmentCount++;
               groupQueue.shift();  // 移除下一个组
           } else {
               // 否则需要两次调整
               adjustmentCount += 2;

               // 重新排列剩余的组
               let rearrangedQueue = [];
               while (groupQueue.length > 0) {
                   let group = groupQueue.shift();

                   if (group[0] === currentGroup[0]) {
                       continue;  // 跳过与当前组号相同的组
                   }

                   if (rearrangedQueue.length === 0 || rearrangedQueue[rearrangedQueue.length - 1][0] !== group[0]) {
                       rearrangedQueue.push([group[0], group[1]]);
                   } else {
                       rearrangedQueue[rearrangedQueue.length - 1][1] += group[1];
                   }
               }
               groupQueue = rearrangedQueue;  // 更新队列
           }
       } else if (currentGroup[1] === 2) {
           // 如果当前组有两个学生
           adjustmentCount += 1;

           // 重新排列剩余的组
           let rearrangedQueue = [];
           while (groupQueue.length > 0) {
               let group = groupQueue.shift();

               if (group[0] === currentGroup[0]) {
                   continue;  // 跳过与当前组号相同的组
               }

               if (rearrangedQueue.length === 0 || rearrangedQueue[rearrangedQueue.length - 1][0] !== group[0]) {
                   rearrangedQueue.push([group[0], group[1]]);
               } else {
                   rearrangedQueue[rearrangedQueue.length - 1][1] += group[1];
               }
           }
           groupQueue = rearrangedQueue;  // 更新队列
       }
   }

   console.log(adjustmentCount);  // 输出调整次数
});

C++

#include <iostream>
#include <vector>
#include <sstream>
#include <queue>
#include <string>

using namespace std;

int main() {
   string initialOrderLine, groupOrderLine;
   getline(cin, initialOrderLine); // 读取初始排队顺序
   getline(cin, groupOrderLine);   // 读取分组排队顺序

   // 将初始排队顺序解析为整数数组
   stringstream initialStream(initialOrderLine);
   vector<int> initialOrder;
   int num;
   while (initialStream >> num) {
       initialOrder.push_back(num);
   }
   int studentCount = initialOrder.size();

   // 将分组排队顺序解析为整数数组
   stringstream groupStream(groupOrderLine);
   vector<int> groupOrder;
   while (groupStream >> num) {
       groupOrder.push_back(num);
   }

   // 创建序号到组号的映射关系数组
   vector<int> groupMapping(studentCount + 1, 0);
   for (int i = 0; i < studentCount; i++) {
       int studentNumber = groupOrder[i];  // 读取每个学生的序号
       groupMapping[studentNumber] = i / 3;  // 每三个学生分为一组，映射组号
   }

   // 创建一个队列用于合并相邻相同组号的学生
   deque<pair<int, int>> groupQueue;
   for (int studentNumber : initialOrder) {
       int groupId = groupMapping[studentNumber];  // 获取学生对应的组号

       if (groupQueue.empty() || groupQueue.back().first != groupId) {
           // 如果队列为空或者最后一个组与当前学生组不同，新增一个组
           groupQueue.emplace_back(groupId, 1);
       } else {
           // 如果最后一个组与当前学生组相同，则增加该组的学生数
           groupQueue.back().second++;
       }
   }

   // 记录需要调整的次数
   int adjustmentCount = 0;
   while (!groupQueue.empty()) {
       pair<int, int> currentGroup = groupQueue.front();  // 取出第一个组
       groupQueue.pop_front();

       if (currentGroup.second == 1) {
           // 如果当前组只有一个学生
           pair<int, int> nextGroup = groupQueue.front();  // 获取下一个组

           while (nextGroup.second == 3) {
               // 如果下一个组的学生数为3，继续获取下一个组
               groupQueue.pop_front();
               nextGroup = groupQueue.front();
           }

           if (nextGroup.first == currentGroup.first && nextGroup.second == 2) {
               // 如果下一个组与当前组组号相同且有两个学生，则需要一次调整
               adjustmentCount++;
               groupQueue.pop_front();  // 移除下一个组
           } else {
               // 否则需要两次调整
               adjustmentCount += 2;

               // 重新排列剩余的组
               deque<pair<int, int>> rearrangedQueue;
               while (!groupQueue.empty()) {
                   pair<int, int> group = groupQueue.front();
                   groupQueue.pop_front();

                   if (group.first == currentGroup.first) {
                       continue;  // 跳过与当前组号相同的组
                   }

                   if (rearrangedQueue.empty() || rearrangedQueue.back().first != group.first) {
                       rearrangedQueue.emplace_back(group.first, group.second);
                   } else {
                       rearrangedQueue.back().second += group.second;
                   }
               }
               groupQueue = rearrangedQueue;  // 更新队列
           }
       } else if (currentGroup.second == 2) {
           // 如果当前组有两个学生
           adjustmentCount += 1;

           // 重新排列剩余的组
           deque<pair<int, int>> rearrangedQueue;
           while (!groupQueue.empty()) {
               pair<int, int> group = groupQueue.front();
               groupQueue.pop_front();

               if (group.first == currentGroup.first) {
                   continue;  // 跳过与当前组号相同的组
               }

               if (rearrangedQueue.empty() || rearrangedQueue.back().first != group.first) {
                   rearrangedQueue.emplace_back(group.first, group.second);
               } else {
                   rearrangedQueue.back().second += group.second;
               }
           }
           groupQueue = rearrangedQueue;  // 更新队列
       }
   }

   // 输出调整次数
   cout << adjustmentCount << endl;

   return 0;
}

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 定义结构体用于存储组号和组内学生数
typedef struct {
   int groupId;
   int studentCount;
} Group;

int main() {
   char initialOrderLine[90001], groupOrderLine[90001];
   fgets(initialOrderLine, sizeof(initialOrderLine), stdin); // 读取初始排队顺序
   fgets(groupOrderLine, sizeof(groupOrderLine), stdin);     // 读取分组排队顺序

   // 将初始排队顺序解析为整数数组
   int initialOrder[30000];
   int studentCount = 0;
   char *token = strtok(initialOrderLine, " ");
   while (token != NULL) {
       initialOrder[studentCount++] = atoi(token);
       token = strtok(NULL, " ");
   }

   // 将分组排队顺序解析为整数数组
   int groupOrder[30000];
   int index = 0;
   token = strtok(groupOrderLine, " ");
   while (token != NULL) {
       groupOrder[index++] = atoi(token);
       token = strtok(NULL, " ");
   }

   // 创建序号到组号的映射关系数组
   int groupMapping[studentCount + 1];
   for (int i = 0; i < studentCount; i++) {
       int studentNumber = groupOrder[i];  // 读取每个学生的序号
       groupMapping[studentNumber] = i / 3;  // 每三个学生分为一组，映射组号
   }

   // 创建一个队列用于合并相邻相同组号的学生
   Group groupQueue[30000];
   int queueSize = 0;
   for (int i = 0; i < studentCount; i++) {
       int studentNumber = initialOrder[i];
       int groupId = groupMapping[studentNumber];  // 获取学生对应的组号

       if (queueSize == 0 || groupQueue[queueSize - 1].groupId != groupId) {
           // 如果队列为空或者最后一个组与当前学生组不同，新增一个组
           groupQueue[queueSize].groupId = groupId;
           groupQueue[queueSize].studentCount = 1;
           queueSize++;
       } else {
           // 如果最后一个组与当前学生组相同，则增加该组的学生数
           groupQueue[queueSize - 1].studentCount++;
       }
   }

   // 记录需要调整的次数
   int adjustmentCount = 0;
   int front = 0;
   while (front < queueSize) {
       Group currentGroup = groupQueue[front];  // 取出第一个组

       if (currentGroup.studentCount == 1) {
           // 如果当前组只有一个学生
           Group nextGroup = groupQueue[front + 1];  // 获取下一个组

           while (nextGroup.studentCount == 3) {
               // 如果下一个组的学生数为3，继续获取下一个组
               front++;
               nextGroup = groupQueue[front + 1];
           }

           if (nextGroup.groupId == currentGroup.groupId && nextGroup.studentCount == 2) {
               // 如果下一个组与当前组组号相同且有两个学生，则需要一次调整
               adjustmentCount++;
               front++;  // 移除下一个组
           } else {
               // 否则需要两次调整
               adjustmentCount += 2;

               // 重新排列剩余的组
               Group rearrangedQueue[30000];
               int rearrangedSize = 0;
               for (int i = front + 1; i < queueSize; i++) {
                   Group group = groupQueue[i];

                   if (group.groupId == currentGroup.groupId) {
                       continue;  // 跳过与当前组号相同的组
                   }

                   if (rearrangedSize == 0 || rearrangedQueue[rearrangedSize - 1].groupId != group.groupId) {
                       rearrangedQueue[rearrangedSize].groupId = group.groupId;
                       rearrangedQueue[rearrangedSize].studentCount = group.studentCount;
                       rearrangedSize++;
                   } else {
                       rearrangedQueue[rearrangedSize - 1].studentCount += group.studentCount;
                   }
               }
               memcpy(groupQueue + front + 1, rearrangedQueue, rearrangedSize * sizeof(Group));  // 更新队列
               queueSize = front + 1 + rearrangedSize;
           }
       } else if (currentGroup.studentCount == 2) {
           // 如果当前组有两个学生
           adjustmentCount += 1;

           // 重新排列剩余的组
           Group rearrangedQueue[30000];
           int rearrangedSize = 0;
           for (int i = front + 1; i < queueSize; i++) {
               Group group = groupQueue[i];

               if (group.groupId == currentGroup.groupId) {
                   continue;  // 跳过与当前组号相同的组
               }

               if (rearrangedSize == 0 || rearrangedQueue[rearrangedSize - 1].groupId != group.groupId) {
                   rearrangedQueue[rearrangedSize].groupId = group.groupId;
                   rearrangedQueue[rearrangedSize].studentCount = group.studentCount;
                   rearrangedSize++;
               } else {
                   rearrangedQueue[rearrangedSize - 1].studentCount += group.studentCount;
               }
           }
           memcpy(groupQueue + front + 1, rearrangedQueue, rearrangedSize * sizeof(Group));  // 更新队列
           queueSize = front + 1 + rearrangedSize;
       }

       front++;
   }

   // 输出调整次数
   printf("%d\n", adjustmentCount);

   return 0;
}