P6564[CF Educational Round 81]Permutation Separation | ||
|
问题描述
给你一个排列$p_1,p_2,\dots,p_n$(即$1\sim n$每个整数都恰好出现一次),其中第$i$个数$p_i$的重量是$a_i$。
首先,你需要将排列划分为非空的两部分组成集合,一个是非空前缀组成的集合、另一个是非空后缀组成的集合。用数学符号描述为,前缀集合$\{p_1,p_2,\dots,p_k\}$,后缀集合$\{p_{k+1},p_{k+2},\dots,p_n\}$,其中$1\leq k\lt n$。
然后,你可以在两个集合之间移动数据。每次操作可以将一个整数从它所在的集合移动到另外一个集合,移动的代价是它的重量。即你需要花费$a_i$的代价才能将$p_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,5$两个数移动到另一个集合达成目标,总代价为$1+1=2$。
请计算达成目标的总代价最小是多少。
输入格式
第一行一个整数$n(2\leq n\leq 2\times 10^5)$,表示排列的长度。
第二行$n$个整数$p_1,p_2,\dots,p_n(1\leq p_i\leq n)$,保证$1\sim n$每个整数恰好出现一次。
第三行$n$个整数$a_1,a_2,\dots,a_n(1\leq a_i\leq 10^9)$。
输出格式
输出一个整数,达成目标的最小总代价。
样例输入
样例输入1:
3
3 1 2
7 1 4
样例输入2:
4
2 4 1 3
5 9 8 3
样例输入3:
6
3 5 1 6 2 4
9 1 9 9 1 9
样例输出
样例输出1:
4
样例输出2:
3
样例输出3:
2