TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P6564
  • 题目
  • P6564[CF Educational Round 81]Permutation Separation
    限制 : 时间限制 : - MS   空间限制 : 262144 KB
    评测说明 : 2s,256MB
    问题描述

    给你一个排列$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


    来源  CF1295E,nodgd搬运