Move It

题目描述

有 $N$ 个编号为 $1$ 到 $N$ 的盒子和 $N$ 个编号为 $1$ 到 $N$ 的物品。物品 $i$ $(1 \leq i \leq N)$ 在盒子 $A_i$ 中，重量为 $W_i$。 你可以反复执行如下操作：选择一个物品并把它移动到另一个盒子，次数可以为零或多次。如果被移动的物品重量为 $w$，则该次操作的代价为 $w$。 求使每个盒子恰好包含一个物品所需的最小总代价。

输入格式

输入从标准输入按以下格式给出： $N$ $A_1$ $A_2$ $\ldots$ $A_N$ $W_1$ $W_2$ $\ldots$ $W_N$

输出格式

输出使每个盒子恰好包含一个物品所需的最小总代价。

5
2 2 3 3 5
33 40 2 12 16

35

12
3 6 7 4 12 4 8 11 11 1 8 11
3925 9785 9752 3587 4013 1117 3937 7045 6437 6208 3391 6309

17254

提示

$1 \leq N \leq 10^{5}$ $1 \leq A_i \leq N$ $(1 \leq i \leq N)$ $1 \leq W_i \leq 10^{4}$ $(1 \leq i \leq N)$ 所有输入值均为整数。通过如下两次移动，可以使每个盒子恰好包含一个物品：

将物品 $1$ 从盒子 $2$ 移到盒子 $1$。代价为 $33$。 将物品 $3$ 从盒子 $3$ 移到盒子 $4$。代价为 $2$。

这两次移动的总代价为 $35$。不可能以小于 $35$ 的代价使每个盒子恰好包含一个物品，因此输出 $35$。

标签: AtCoder|abc360C

来源

AtCoder|abc360C