2026年 北马其顿编程竞赛 (Macedonian programming contests 2026)

赛事等级： 校级选拔赛 (School competition)
内容类型： 竞赛题目 (Competition tasks)

题目名称：书架 (Полици со книги)

题目描述

在一个书架（第一排）上摆放着 $N$ 本不同的书（为了方便说明，我们假设每本书都标记有 $1$ 到 $N$ 之间的一个唯一编号）。在它下方有另一个书架（第二排），上面摆放着同样的一批书，但顺序不同。

萨拉（Sara）只能触及第二排书架。她每次可以拿起两本书并交换它们的位置。

萨拉决定重新排列第二排书架上的书，使其顺序与第一排书架完全一致。由于她不想浪费时间做不必要的交换，她希望以最少的交换次数完成这项工作。你的任务是确定达到目标顺序所需的最少交换次数。

输入格式

• 第一行包含一个整数 $N$ ($1 \le N \le 100,000$)，代表书籍的数量。
• 第二行包含 $N$ 个整数 $A_i$ ($1 \le A_i \le N$)，代表第一排书架上书籍的顺序，由空格分隔。
• 第三行包含 $N$ 个整数 $B_i$ ($1 \le B_i \le N$)，代表第二排书架上书籍的初始顺序，由空格分隔。

注意：

• 20% 的测试点满足：$N \le 10$。
• 另外 50% 的测试点满足：第一排书架上的书已经按 $1, 2, \dots, N$ 的顺序排好。

输出格式

• 输出一个整数，代表将第二排书架调整至与第一排一致所需的最少交换次数。

限制条件

• 时间限制： 200 毫秒
• 内存限制： 16 MB

样例说明

• 输入：

  4
  1 3 2 4
  4 2 3 1
  

• 输出：

  2
  

• 解释： 在第二排书架上，首先交换 4 和 1，然后再交换 2 和 3。只需 2 次交换即可匹配第一排的 1 3 2 4。

版权及来源信息

• 项目： Macedonian Programming Contests (北马其顿编程竞赛)
• 年份： 2026
• 主办/版权方： Združenie na informatičari na Makedonija (ZIM / 北马其顿计算机科学家协会)
• 语言： 马其顿语 (Original in Macedonian)