返回目录

题目描述

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）

示例：

Python算法源码

def split_input(separator):
    input_str = input().strip()
    return list(map(int, input_str.split(separator)))

def confirm(queue, confirmed_group_id):
    back_queue = []
    for block in queue:
        if block[0] != confirmed_group_id:
            back_queue.append(block)
    new_queue = []
    for i in range(len(back_queue)):
        if i == 0 or back_queue[i][0] != back_queue[i - 1][0]:
            new_queue.append(back_queue[i])
        else:
            new_queue[-1][1] += back_queue[i][1]
    return new_queue

def main():
    # 原始序列
    nums = split_input(' ')
    original_size = len(nums)
    # 排序后的序列
    sorted_nums = split_input(' ')
    sorted_size = len(sorted_nums)

    # 将索引映射到组号，索引表示顺序，值表示组号
    group = [0] * (sorted_size + 1)
    for i, num in enumerate(sorted_nums):
        group[num] = i // 3

    # 合并相邻的组号相同的块并计数
    queue = []
    for num in nums:
        group_id = group[num]
        if not queue or queue[-1][0] != group_id:
            queue.append([group_id, 1])
        else:
            queue[-1][1] += 1

    # 记录调整次数
    moved_count = 0
    while queue:
        first = queue.pop(0)
        if first[1] == 1:
            if len(queue) > 0 and queue[0][0] == first[0] and queue[0][1] == 2:
                moved_count += 1
                queue.pop(0)
            else:
                moved_count += 2
                queue = confirm(queue, first[0])
        elif first[1] == 2:
            moved_count += 1
            queue = confirm(queue, first[0])

    print(moved_count)

if __name__ == "__main__":
    main()

C算法源码

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

#define MAX_SIZE 1000

// 定义结构体 Block，用于表示每个块的信息
struct Block {
    int groupId;  // 组号
    int count;    // 数量
};

// 创建新的 Block 结构体实例
struct Block createBlock(int groupId, int count) {
    struct Block newBlock;
    newBlock.groupId = groupId;
    newBlock.count = count;
    return newBlock;
}

// 根据分隔符 separator 对输入进行拆分，并返回拆分后的整数数组和数组大小
int* splitCin(char separator, int* size) {
    char input[MAX_SIZE];
    fgets(input, MAX_SIZE, stdin);
    input[strcspn(input, "\n")] = 0;

    int* res = (int*)malloc(MAX_SIZE * sizeof(int));
    int count = 0;

    char* token = strtok(input, &separator);

    while (token != NULL) {
        res[count++] = atoi(token);
        token = strtok(NULL, &separator);
    }

    *size = count;
    return res;
}

// 确认并更新队列，移除已确认的子块，并尝试合并前后的相同组号的子块
struct Block* confirm(struct Block *queue, int *queue_size, int confirmed_groupId) {
    struct Block* back_queue = (struct Block*)malloc(MAX_SIZE * sizeof(struct Block));
    int back_size = 0;

    for (int i = 0; i < *queue_size; i++) {
        if (queue[i].groupId == confirmed_groupId) {
            continue;
        }

        if (back_size == 0 || back_queue[back_size - 1].groupId != queue[i].groupId) {
            back_queue[back_size++] = createBlock(queue[i].groupId, queue[i].count);
        } else {
            back_queue[back_size - 1].count += queue[i].count;
        }
    }

    *queue_size = back_size;
    return back_queue;
}

int main() {
    // 原始序列
    int original_size;
    int* nums = splitCin(' ', &original_size);
    // 排序后的序列
    int sorted_size;
    int* sorted_nums = splitCin(' ', &sorted_size);

    // 将索引映射到组号，索引表示顺序，值表示组号
    int* group = (int*)malloc((sorted_size + 1) * sizeof(int));
    memset(group, 0, (sorted_size + 1) * sizeof(int));

    for (int i = 0; i < sorted_size; i++) {
        int num = sorted_nums[i];
        group[num] = i / 3;
    }

    // 合并相邻的组号相同的块并计数
    struct Block* queue = (struct Block*)malloc(MAX_SIZE * sizeof(struct Block));
    int queue_size = 0;

    for (int i = 0; i < original_size; i++) {
        int groupId = group[nums[i]];

        if (queue_size == 0 || queue[queue_size - 1].groupId != groupId) {
            queue[queue_size++] = createBlock(groupId, 1);
        } else {
            queue[queue_size - 1].count++;
        }
    }

    // 记录调整次数
    int moved_count = 0;
    while (queue_size > 0) {
        struct Block first = queue[0];
        for (int i = 0; i < queue_size - 1; i++) {
            queue[i] = queue[i + 1];
        }
        queue_size--;

        if (first.count == 1) {
            struct Block x = queue[0];

            while (x.count == 3 && queue_size > 0) {
                for (int i = 0; i < queue_size - 1; i++) {
                    queue[i] = queue[i + 1];
                }
                queue_size--;
                x = queue[0];
            }

            if (x.groupId == first.groupId && x.count == 2 && queue_size > 0) {
                moved_count++;
                for (int i = 0; i < queue_size - 1; i++) {
                    queue[i] = queue[i + 1];
                }
                queue_size--;
            } else {
                moved_count += 2;
                struct Block* new_queue = confirm(queue, &queue_size, first.groupId);
                free(queue);
                queue = new_queue;
            }
        } else if (first.count == 2) {
            moved_count += 1;
            struct Block* new_queue = confirm(queue, &queue_size, first.groupId);
            free(queue);
            queue = new_queue;
        }
    }

    printf("%d\n", moved_count);

    free(nums);
    free(sorted_nums);
    free(group);
    free(queue);

    return 0;
}

Java算法源码

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Block {
    int groupId;
    int count;

    public Block(int groupId, int count) {
        this.groupId = groupId;
        this.count = count;
    }
}

public class Main {
    public static int[] splitInput(char separator) {
        Scanner scanner = new Scanner(System.in);
        String inputStr = scanner.nextLine().trim();
        String[] tokens = inputStr.split(String.valueOf(separator));
        int[] nums = new int[tokens.length];
        for (int i = 0; i < tokens.length; i++) {
            nums[i] = Integer.parseInt(tokens[i]);
        }
        return nums;
    }

    public static List<Block> confirm(List<Block> queue, int confirmedGroupId) {
        List<Block> backQueue = new ArrayList<>();
        for (Block block : queue) {
            if (block.groupId != confirmedGroupId) {
                backQueue.add(block);
            }
        }
        List<Block> newQueue = new ArrayList<>();
        for (int i = 0; i < backQueue.size(); i++) {
            if (i == 0 || backQueue.get(i).groupId != backQueue.get(i - 1).groupId) {
                newQueue.add(backQueue.get(i));
            } else {
                newQueue.get(newQueue.size() - 1).count += backQueue.get(i).count;
            }
        }
        return newQueue;
    }

    public static void main(String[] args) {
        // 原始序列
        int[] nums = splitInput(' ');
        int originalSize = nums.length;
        // 排序后的序列
        int[] sortedNums = splitInput(' ');
        int sortedSize = sortedNums.length;

        // 将索引映射到组号，索引表示顺序，值表示组号
        int[] group = new int[sortedSize + 1];
        for (int i = 0; i < sortedSize; i++) {
            int num = sortedNums[i];
            group[num] = i / 3;
        }

        // 合并相邻的组号相同的块并计数
        List<Block> queue = new ArrayList<>();
        for (int num : nums) {
            int groupId = group[num];
            if (queue.isEmpty() || queue.get(queue.size() - 1).groupId != groupId) {
                queue.add(new Block(groupId, 1));
            } else {
                queue.get(queue.size() - 1).count++;
            }
        }

        // 记录调整次数
        int movedCount = 0;
        while (!queue.isEmpty()) {
            Block first = queue.remove(0);
            if (first.count == 1) {
                if (!queue.isEmpty() && queue.get(0).groupId == first.groupId && queue.get(0).count == 2) {
                    movedCount++;
                    queue.remove(0);
                } else {
                    movedCount += 2;
                    queue = confirm(queue, first.groupId);
                }
            } else if (first.count == 2) {
                movedCount++;
                queue = confirm(queue, first.groupId);
            }
        }

        System.out.println(movedCount);
    }
}