AT_abc360_c [ABC360C] Move It

题目描述

有 $N$ 个编号为 $1$ 到 $N$ 的箱子，以及 $N$ 个编号为 $1$ 到 $N$ 的行李。行李 $i$（$1 \leq i \leq N$）目前在编号为 $A_i$ 的箱子中，重量为 $W_i$。

你可以选择一个行李，并将其移动到其他任意一个箱子中，这个操作可以重复进行 $0$ 次或多次。每次移动行李时，若被移动行李的重量为 $w$，则需要花费 $w$ 的代价。

请你求出，使得每个箱子里正好有一个行李所需的总代价的最小值。

输入格式

输入以如下格式从标准输入读入：

$N$ $A_1$ $A_2$ $\ldots$ $A_N$ $W_1$ $W_2$ $\ldots$ $W_N$

输出格式

输出使得每个箱子里正好有一个行李所需的总代价的最小值。

输入输出样例 #1

输入 #1

5
2 2 3 3 5
33 40 2 12 16

输出 #1

35

输入输出样例 #2

输入 #2

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

输出 #2

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

通过以下两次行李移动，可以使每个箱子里正好有一个行李：

• 将行李 $1$ 从箱子 $2$ 移动到箱子 $1$，此时花费 $33$。
• 将行李 $3$ 从箱子 $3$ 移动到箱子 $4$，此时花费 $2$。

这两次移动的总代价为 $35$。无法通过低于 $35$ 的总代价使每个箱子里正好有一个行李，因此输出 $35$。

由 ChatGPT 4.1 翻译