AT_abc261_f [ABC261F] Sorting Color Balls

题目描述

有 $N$ 个球从左到右排成一列。第 $i$ 个球的颜色为 $C_i$，上面写着整数 $X_i$。

高桥君的目标是将球重新排列，使得从左到右看时，球上写的数字是非递减的。换句话说，高桥君的目标是，对于任意 $1\leq i\leq N-1$，第 $i+1$ 个球上写的数字不小于第 $i$ 个球上写的数字。

为达成目标，高桥君可以进行任意多次（可以为 $0$ 次）如下操作：

选择满足 $1\leq i\leq N-1$ 的整数 $i$。
如果第 $i$ 个球和第 $i+1$ 个球的颜色不同，则需要支付 $1$ 的代价（如果颜色相同则无需支付代价）。
交换第 $i$ 个球和第 $i+1$ 个球的位置。

请你求出高桥君为达成目标所需支付的最小总代价。

输入格式

输入按以下格式从标准输入给出。

$N$
$C_1\ C_2\ \ldots\ C_N$
$X_1\ X_2\ \ldots\ X_N$

输出格式

输出高桥君为达成目标所需支付的最小总代价。

输入输出样例 #1

输入 #1

5
1 5 2 2 1
3 2 1 2 1

输出 #1

6

输入输出样例 #2

输入 #2

3
1 1 1
3 2 1

输出 #2

0

输入输出样例 #3

输入 #3

3
3 1 2
1 1 2

输出 #3

0

说明/提示

限制条件

• $2\leq N\leq 3\times 10^5$
• $1\leq C_i\leq N$
• $1\leq X_i\leq N$
• 输入均为整数

样例解释 1

用 $(颜色, 数字)$ 表示每个球的信息。初始状态为 $(1,3)$、$(5,2)$、$(2,1)$、$(2,2)$、$(1,1)$。例如，高桥君可以按如下方式操作：

• 交换第 $1$ 个球（颜色 $1$）和第 $2$ 个球（颜色 $5$）。球的顺序变为 $(5,2)$、$(1,3)$、$(2,1)$、$(2,2)$、$(1,1)$。
• 交换第 $2$ 个球（颜色 $1$）和第 $3$ 个球（颜色 $2$）。球的顺序变为 $(5,2)$、$(2,1)$、$(1,3)$、$(2,2)$、$(1,1)$。
• 交换第 $3$ 个球（颜色 $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$ 个球（颜色 $2$）和第 $4$ 个球（颜色 $1$）。球的顺序变为 $(5,2)$、$(2,1)$、$(1,1)$、$(2,2)$、$(1,3)$。
• 交换第 $1$ 个球（颜色 $5$）和第 $2$ 个球（颜色 $2$）。球的顺序变为 $(2,1)$、$(5,2)$、$(1,1)$、$(2,2)$、$(1,3)$。
• 交换第 $2$ 个球（颜色 $5$）和第 $3$ 个球（颜色 $1$）。球的顺序变为 $(2,1)$、$(1,1)$、$(5,2)$、$(2,2)$、$(1,3)$。

在最后一次操作后，球上写的数字依次为 $1,1,2,2,3$，高桥君达成了目标。第 $1,2,3,5,6,7$ 次操作各需支付 $1$ 的代价，因此总代价为 $6$，这是最小值。注意第 $4$ 次操作时，交换的两个球颜色相同，因此不需要支付代价。

样例解释 2

所有球的颜色都相同，因此交换球时不需要支付任何代价。

样例解释 3

高桥君无需进行任何操作即可达成目标。

由 ChatGPT 4.1 翻译