返回目录

题目描述

n (3≤n≤90000 且可以整除 3 )个学生排成一排，学生编号分别是 1 到 n，n 为 3 的整倍数，老师随机抽签决定将所有学生分成 m 个 3 人的小组（n == 3 * m） 。

为了便于同组学生交流，老师决定将小组成员安排到一起，也就是同组成员彼此相连，同组任意两个成员之间无其它组的成员。

因此老师决定调整队伍，老师每次可以调整任何一名学生到队伍的任意位置，计为调整了一次， 请计算最少调整多少次可以达到目标。

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

输入描述

第一行输入初始排队顺序序列

第二行输入分组排队顺序序列

输出描述

输出一个整数x，表示至少调整x次站位

示例：

解题思路

为了计算给定输入序列的最少调整次数，我们需要遵循以下步骤：

1. 映射学生到组号：根据第二行的分组排队序列，将每个学生映射到一个组号上。每3个学生属于同一组。
2. 转换初始序列为组号序列：根据映射，将初始排队序列转换为对应的组号序列。
3. 记录组号的出现位置：为每个组创建一个列表，记录该组学生在初始序列中的位置。

4. 分析并计算调整次数：

   • 对于每个组，检查其成员在初始序列中的位置是否连续。如果不连续，则需要进行调整。
   • 特别地，如果组内成员已经是连续的，则不需要调整。
   • 考虑到不需要关心组间的顺序，只需关注组内成员的连续性，我们可以通过计算每个组内成员的间隔来确定是否需要调整。
5. 输出最少调整次数。

根据以上思路，下面是对应的模拟计算过程：

• 输入序列是 4 2 8 5 3 6 1 9 7，分组序列是 6 3 1 2 4 8 7 9 5。
• 分组为：{6,3,1}，{2,4,8}，{7,9,5}。
• 初始序列转换为组号序列：[1, 1, 1, 2, 0, 0, 0, 2, 2]。
• 组号 0的出现位置为 [4, 5, 6]，组号 1的出现位置为 [0, 1, 2]，组号 2的出现位置为 [3, 7, 8]。
• 分析发现，组号 0和 1的成员在初始序列中不是完全连续，但只需进行一次调整（将数字 5移动到 1后面），即可使所有组内成员连续。
• 因此，最少调整次数为 1。

Python算法源码

def main():
    # 读取第一行并转换为整型数组
    nums = list(map(int, input().split()))

    # 读取第二行并转换为整型数组
    line2 = list(map(int, input().split()))

    n = len(nums)  # 排队的总人数

    # 创建一个映射字典，用于将序号映射到组号（每3个人为一组）
    mapping = {line2[i]: i // 3 for i in range(n)}

    # 将初始序号数组转换为对应的组号数组
    nums = [mapping[num] for num in nums]

    # 创建一个字典的列表，用于存储每个组号出现的位置
    positions = [[] for _ in range(n // 3)]
    for i in range(n):
        positions[nums[i]].append(i)  # 将当前位置添加到对应组号的位置列表中

    # 初始化调整位置次数为0
    moved_count = 0

    # 遍历每个组的位置列表，检查是否需要调整位置
    for pos_list in positions:
        if len(pos_list) == 3:
            # 如果一个组有3个成员，检查他们是否连续
            if pos_list[1] - pos_list[0] > 1 or pos_list[2] - pos_list[1] > 1:
                moved_count += 1  # 如果不连续，至少需要一次调整
        elif len(pos_list) == 2:
            # 如果一个组有2个成员，检查他们之间的间隔
            if pos_list[1] - pos_list[0] > 2:
                moved_count += 1  # 如果间隔超过2，需要一次调整
        elif len(pos_list) == 1:
            # 如果一个组只有1个成员，最坏情况需要两次调整
            moved_count += 2

    # 为了避免过度计算，通过计算组间的交错来可能减少调整次数
    seen_groups = set()  # 用于记录已经遇到的组号
    adjustments = 0  # 记录因组间交错导致的调整次数
    for num in nums:
        if num not in seen_groups:
            # 如果是首次遇到这个组号，添加到已遇到组号的集合中
            seen_groups.add(num)
        else:
            # 如果之前已经遇到过这个组号，说明存在交错，可能需要调整
            adjustments += 1

    # 最终的调整次数是之前计算的调整次数和因交错导致的调整次数中的较小值
    moved_count = min(moved_count, adjustments)

    # 输出最小调整次数
    print(moved_count)

if __name__ == "__main__":
    main()

C算法源码

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

int main() {
    int nums[1000], line2[1000];

    // 读取第一行并转换为整型数组
    scanf("%d", &nums[0]);
    for(int i = 1; i < 1000; i++){
        if(getchar() == '\n') break;
        scanf("%d", &nums[i]);
    }

    // 读取第二行并转换为整型数组
    scanf("%d", &line2[0]);
    for(int i = 1; i < 1000; i++){
        if(getchar() == '\n') break;
        scanf("%d", &line2[i]);
    }

    // 创建一个映射数组，用于将序号映射到组号（每3个人为一组）
    int map[1000] = {0};
    int n = 0;
    for (int i = 0; i < 1000; i++) {
        if (line2[i] != 0) {
            map[line2[i]] = n / 3;
            n++;
        } else {
            break;
        }
    }

    // 将初始序号数组转换为对应的组号数组
    for (int i = 0; i < n; i++) {
        nums[i] = map[nums[i]];
    }

    // 创建一个数组列表的数组，用于存储每个组号出现的位置
    int positions[1000][3] = {0};
    for (int i = 0; i < n; i++) {
        int group_num = nums[i];
        int index = 0;
        while (positions[group_num][index] != 0) {
            index++;
        }
        positions[group_num][index] = i; // 将当前位置添加到对应组号的位置列表中
    }

    // 初始化调整位置次数为0
    int moved_count = 0;

    // 遍历每个组的位置列表，检查是否需要调整位置
    for (int i = 0; i < n / 3; i++) {
        int *pos_list = positions[i];
        int len = 0;
        while (pos_list[len] != 0) {
            len++;
        }
        if (len == 3) {
            // 如果一个组有3个成员，检查他们是否连续
            if (pos_list[1] - pos_list[0] > 1 || pos_list[2] - pos_list[1] > 1) {
                moved_count++; // 如果不连续，至少需要一次调整
            }
        } else if (len == 2) {
            // 如果一个组有2个成员，检查他们之间的间隔
            if (pos_list[1] - pos_list[0] > 2) {
                moved_count++; // 如果间隔超过2，需要一次调整
            }
        } else if (len == 1) {
            // 如果一个组只有1个成员，最坏情况需要两次调整
            moved_count += 2;
        }
    }

    // 为了避免过度计算，通过计算组间的交错来可能减少调整次数
    int seen_groups[1000] = {0}; // 用于记录已经遇到的组号
    int adjustments = 0; // 记录因组间交错导致的调整次数
    for (int i = 0; i < n; i++) {
        int num = nums[i];
        if (seen_groups[num] == 0) {
            // 如果是首次遇到这个组号，添加到已遇到组号的集合中
            seen_groups[num] = 1;
        } else {
            // 如果之前已经遇到过这个组号，说明存在交错，可能需要调整
            adjustments++;
        }
    }

    // 最终的调整次数是之前计算的调整次数和因交错导致的调整次数中的较小值
    moved_count = (moved_count < adjustments) ? moved_count : adjustments;

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

    return 0;
}

Java算法源码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        final int MAX_SIZE = 1000; // 假设最大输入长度

        int[] nums = new int[MAX_SIZE];
        int[] line2 = new int[MAX_SIZE];
        int[] map = new int[MAX_SIZE + 1];
        int[][] positions = new int[MAX_SIZE][3]; // 存储每个组号出现的位置
        int[] groupSize = new int[MAX_SIZE]; // 记录每个组的成员数量

        // 读取第一行并转换为整型数组
        String[] firstLine = scanner.nextLine().split(" ");
        int n = firstLine.length;
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(firstLine[i]);
        }

        // 读取第二行并转换为整型数组
        String[] secondLine = scanner.nextLine().split(" ");
        for (int i = 0; i < n; i++) {
            line2[i] = Integer.parseInt(secondLine[i]);
        }

        // 创建映射数组，将序号映射到组号（每3个人为一组）
        for (int i = 0; i < n; i++) {
            map[line2[i]] = i / 3;
        }

        // 将初始序号数组转换为对应的组号数组
        for (int i = 0; i < n; i++) {
            nums[i] = map[nums[i]];
            positions[nums[i]][groupSize[nums[i]]++] = i;
        }

        // 初始化调整位置次数为0
        int movedCount = 0;

        // 遍历每个组的位置列表，检查是否需要调整位置
        for (int i = 0; i < n / 3; i++) {
            if (groupSize[i] == 3) {
                if (positions[i][1] - positions[i][0] > 1 || positions[i][2] - positions[i][1] > 1) {
                    movedCount++;
                }
            } else if (groupSize[i] == 2) {
                if (positions[i][1] - positions[i][0] > 2) {
                    movedCount++;
                }
            } else if (groupSize[i] == 1) {
                movedCount += 2;
            }
        }

        // 为了避免过度计算，通过计算组间的交错来可能减少调整次数
        int[] seenGroups = new int[MAX_SIZE]; // 用于记录已经遇到的组号
        int adjustments = 0; // 记录因组间交错导致的调整次数
        for (int num : nums) {
            if (seenGroups[num] == 0) {
                seenGroups[num] = 1;
            } else {
                adjustments++;
            }
        }

        // 最终的调整次数是之前计算的调整次数和因交错导致的调整次数中的较小值
        movedCount = Math.min(movedCount, adjustments);

        // 输出最小调整次数
        System.out.println(movedCount);
    }
}