传统题 1000ms 256MiB

波奇农场

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem Description

继mygo图中 mygo 与 mujika 相亲相爱之后,他们两个乐队想继续增进关系,因此来到波奇农场进行合宿活动。

好巧不巧,波奇农场暗地里有一个 livehouse,还有驻唱乐队 kessoku band 以及超人气角色 guitar hero,为了一争高下,mygo_mujika 决定与 kessoku band 在 livehouse 外的农场进行演唱。

眼看诗超绊以及吉他与孤独与蓝色星球等歌曲造成了极大的噪音污染,为了不影响农场植物的生长,农场主ComistryMo决定出手调节。

已知 mygo_mujika 以及 kessoku band 各占据一块长度为 n 的地盘,并且两个乐队人数相同,两个乐队中每个成员都有一个独立的编号,两个乐队的编号都为从1到n的排列,对于从1到n的中每个编号i,都有一个值aia_{i},现在ComistryMo需要构造出a数组,使得两乐队对应位置的编号的值之差的绝对值之和最小。但ComistryMo还有其他事情要做,所以能请你们帮帮他吗?

一句话题意:两个长度为n的排列p1p_{1}和p2p_{2},请你构造排列aa,使得∑i=1nabs(a[p1[i]]−a[p2[i]])\sum_{i=1}^n abs(a[p1[i]] - a[p2[i]])的值最小,并且给出最小值。

Input Format

第一行包含一个整数n,表示排列p1p_{1}和p2p_{2}的长度。

第二行给出n个数字,表示p11p1_1到p1np1_n (1 <= p1ip1_i <= n)。

第三行给出n个数字,表示p21p2_1到p2np2_n (1 <= p2ip2_i <= n)。

Output Format

输出一行一个整数,表示最小值

Sample

样例输入1

5
1 2 3 4 5
5 4 3 2 1

样例输出1

4

样例输入2

5
1 2 3 4 5
2 3 1 5 4

样例输出2

6

样例输入3

5
1 2 3 4 5
3 1 4 5 2

样例输出3

8

Hint

1≤n≤2×1051\leq n \leq 2\times 10^5

重庆邮电大学第十六届ACM程序设计大赛(现场赛)

未参加
状态
已结束
规则
XCPC
题目
12
开始于
2023-10-15 13:10
结束于
2023-10-15 18:10
持续时间
5 小时
主持人
参赛人数
0