分数: 500 点
问题陈述
有 N 球从左到右排列。 的颜色 i左边第一个球是颜色 C_i,和一个整数 上面写着 X_i 。
高桥想要重新排列球,使得球上写的整数从左到右不递减。 换句话说,他的目标是达到这样一种情况:对于每一个 1\leq i\leq N-1,写在 (i+1)左边第一个球大于或等于上面写的数字 i左边第一个球。
为此,Takahashi 可以重复以下操作任意次数(可能为零):
选择一个整数 i 这样 1\leq i\leq N-1.
如果颜色 i-th 和 (i+1)左起第 个球不同,支付成本 1。 (如果颜色相同则不产生任何费用)。
交换 i-th 和 (i+1)从左边数第一个球。
求高桥实现其目标所需支付的最低总成本。
约束
- 2 \leq N \leq 3\times 10^5
- 1\leq C_i\leq N
- 1\leq X_i\leq N
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N C_1 C_2 \ldots C_N X_1 X_2 \ldots X_N
输出
以整数形式打印高桥需要支付的最小总成本。
示例输入 1
5 1 5 2 2 1 3 2 1 2 1
示例输出 1
6
让我们将球表示为 (颜色, 整数)。 初始情况是 (1,3), (5,2), (2,1), (2,2), (1,1)。 以下是 Takahashi 可能的操作顺序:
- 交换 1-st 球(颜色 1)和 2-nd 球(颜色 5)。现在球已按顺序排列 (5,2), (1,3), (2,1), (2,2), (1,1).
- 交换 2-nd 球(颜色 1)和 3-rd 球(颜色 2)。现在球已按顺序排列 (5,2), (2,1), (1,3), (2,2), (1,1).
- 交换 3-rd 球(颜色 1)和 4第一个球(颜色 2)。现在球已按顺序排列 (5,2), (2,1), (2,2), (1,3), (1,1).
- 交换 4第一个球(颜色 1)和 5第一个球(颜色 1)。现在球已按顺序排列 (5,2), (2,1), (2,2), (1,1), (1,3).
- 交换 3-rd 球(颜色 2)和 4第一个球(颜色 1)。现在球已按顺序排列(5,2), (2,1), (1,1), (2,2), (1,3).
- 交换 1-st 球(颜色 5)和 2-nd 球(颜色 2)。现在球已按顺序排列 (2,1), (5,2), (1,1), (2,2), (1,3).
- 交换 2-nd 球(颜色 5)和 3-rd 球(颜色 1)。现在球已按顺序排列 (2,1), (1,1), (5,2), (2,2), (1,3).
最后一次操作后,球上写的数字是 1,1,2,2,3 从左到右,这就达到了高桥的目的。
的 1-st, 2-nd, 3-rd, 5-th, 6-th,以及 7-th 操作产生的成本为 1 每个,总共 6,这是最小值。 请注意, 4-th 操作不会产生成本,因为球都是彩色的 1.
示例输入 2
3 1 1 1 3 2 1
示例输出 2
0
所有球的颜色相同,因此交换球不会产生任何费用。
示例输入 3
3 3 1 2 1 1 2
示例输出 3
0
高桥的目的无需任何操作就已经达到。