Sorting Color Balls

题目描述

有 $N$ 个球从左到右排列。 从左数第 $i$ 个球的颜色为 Color $C_i$，球上写着整数 $X_i$。 Takahashi 想要重新排列这些球，使得从左到右球上写的整数是非递减的。 换言之，他的目标是达到这样一种情况：对任意 $1\leq i\leq N-1$，从左数第 $(i+1)$ 个球上写的数不小于从左数第 $i$ 个球上写的数。 为此，Takahashi 可以重复以下操作任意次（也可以为零次）：

选择一个整数 $i$ 满足 $1\leq i\leq N-1$.
如果从左数第 $i$ 个和第 $(i+1)$ 个球的颜色不同，则支付代价 $1$。
（如果颜色相同则不产生代价）。
交换从左数第 $i$ 个和第 $(i+1)$ 个球。

求 Takahashi 为实现他的目标所需支付的最小总代价。

输入格式

输入从标准输入按以下格式给出： $N$ $C_1$ $C_2$ $\ldots$ $C_N$ $X_1$ $X_2$ $\ldots$ $X_N$

输出格式

输出 Takahashi 为实现他的目标所需支付的最小总代价，作为一个整数。

5
1 5 2 2 1
3 2 1 2 1

6

3
1 1 1
3 2 1

0

3
3 1 2
1 1 2

0

提示

$2 \leq N \leq 3\times 10^5$ $1\leq C_i\leq N$ $1\leq X_i\leq N$ 输入中的所有值均为整数。我们用 $(\text{颜色},\ \text{整数})$ 表示一个球。 初始情况为 $(1,3)$、$(5,2)$、$(2,1)$、$(2,2)$、$(1,1)$。 下面给出 Takahashi 的一种可能的操作序列：

交换第 $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$，达到了 Takahashi 的目标。 第 $1$、$2$、$3$、$5$、$6$、$7$ 次操作各产生代价 $1$，总计 $6$，这是最小值。 注意第 $4$ 次操作不产生代价，因为两球均为颜色 $1$。
所有球颜色相同时，交换不产生代价。
Takahashi 的目标在无需任何操作的情况下已被满足。

标签: AtCoder|abc261F

来源

AtCoder|abc261F