「AHOI / HNOI2018」排列
问题描述
给定 $n$ 个整数 $a_1, a_2, …, a_n(0 \le a_i \le n)$，以及 $n$ 个整数 $w_1, w_2, …, w_n$。称 $a_1, a_2, …, a_n$ 的一个排列 $a_{p[1]}, a_{p[2]}, …, a_{p[n]}$ 为 $a_1, a_2, …, a_n$ 的一个合法排列，当且仅当该排列满足：对于任意的 $k$ 和任意的 $j$，如果 $j \le k$，那么 $a_{p[j]}$ 不等于 $p[k]$。（换句话说就是：对于任意的 $k$ 和任意的 $j$，如果 $p[k]$ 等于 $a_{p[j]}$，那么 $k<j$。）
定义这个合法排列的权值为 $w_{p[1]} + 2w_{p[2]} + … + nw_{p[n]}$。你需要求出在所有合法排列中的最大权值。如果不存在合法排列，输出 $-1$。
样例解释中给出了合法排列和非法排列的实例。
输入格式
第一行一个整数 $n$。
接下来一行 $n$ 个整数，表示 $a_1,a_2,…, a_n$。
接下来一行 $n$ 个整数，表示 $w_1,w_2,…,w_n$。
输出格式
输出一个整数表示答案。
样例输入
3
0 1 1
5 7 3
样例输出
32
提示
对于前 $20\%$ 的数据，$1 \le n \le 10$；
对于前 $40\%$ 的数据，$1 \le n \le 15$；
对于前 $60\%$ 的数据，$1 \le n \le 1000$；
对于前 $80\%$ 的数据，$1 \le n \le 100000$；
对于 $100\%$ 的数据，$1 \le n \le 500000$，$0 \le a_i \le n (1 \le i \le n)$，$1 \le w_i \le 10^9$ ，所有 $w_i$ 的和不超过 $1.5 \times 10^{13}$。
弄清楚题意后发现，题目要求的就是$a_{a_i}$在新排列中必须在$a_i$之前，那么我们从$i\rightarrow a_i$连边，这样的话就变成一颗以0为根的树，那么要求就是必须先选父亲才能选儿子。
要求权值最大等价于先选权值小的，那么考虑全局最小值优先选。如果当前全局最小值的父亲为0，那么直接选。
否则它一定在选了父亲之后第一个选，因此可以将它和它的父亲缩到一起，考虑缩点后的权值是多少，这里比较巧妙，实际上权值给成$\frac{\sum w_i}{size}$就是对的，具体证明我们考虑假如先选缩点后的$(a_1,a_2,…,a_k)$比先选$a_{k+1},…,a_n$优，那么意味着
$$
a_1+2a_2+…+ka_k+(k+1)a_{k+1}+…+na_n \geq a_{k+1}+…+(n-k)a_n+(n-k+1)a_1+…+na_k
$$
那么移项就得到
$$
(n-k)(a_1+a_2+…+a_k)\leq k(a_{k+1}+…+a_n)
$$
那么容易发现这样做是对的。因此只需要用并查集+堆来维护就行了。
代码：
1 |
|