CF1295E Permutation Separation

给定一个排列 $p_1, p_2, \dots, p_n$（一个包含 $1$ 到 $n$ 的每个整数且每个只出现一次的数组）。排列中第 $i$ 个元素的权值为 $a_i$。 首先，你需要将排列分成两个非空集合——前缀和后缀。更正式地说，第一个集合包含元素 $p_1, p_2, \dots, p_k$，第二个集合包含 $p_{k+1}, p_{k+2}, \dots, p_n$，其中 $1 \le k < n$。 之后，你可以在两个集合之间移动元素。你允许的操作是：选择第一个集合中的某个元素并将其移动到第二个集合，或者反过来（从第二个集合移动到第一个集合）。每移动一个 $p_i$ 元素，你需要支付 $a_i$ 美元。 你的目标是使得第一个集合中的每个元素都小于第二个集合中的每个元素。注意，如果某个集合为空，则该条件自动满足。 例如，如果 $p = [3, 1, 2]$ 且 $a = [7, 1, 4]$，最优策略是：将 $p$ 分为 $[3, 1]$ 和 $[2]$ 两部分，然后将 $2$ 元素移到第一个集合（花费 $4$）。如果 $p = [3, 5, 1, 6, 2, 4]$，$a = [9, 1, 9, 9, 1, 9]$，最优策略是：将 $p$ 分为 $[3, 5, 1]$ 和 $[6, 2, 4]$，然后将 $2$ 元素移到第一个集合（花费 $1$），再将 $5$ 元素移到第二个集合（也花费 $1$）。 请计算你需要花费的最少美元数。

第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）——排列的长度。 第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$）。保证该序列是 $1$ 到 $n$ 的一个排列。 第三行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）。

输出一个整数，表示你需要花费的最少美元数。

由 ChatGPT 4.1 翻译