← 返回题目列表

AtCoder · typical90_n

014. 我们曾经一起唱过一首歌(★3)

中文机器翻译题面 查看原题

配点: 3 点

問題文

在AGC高速公路上 N 小学生住在这里。 i (1 \leq i \leq N) 的房子位于 A_i 在。
另外,小学 N 学校已建成,是一所小学。 j (1 \leq j \leq N) 是位置 B_j 在。
住在AGC凯多的小学生们性格都很差,而且彼此之间的关系也不好,所以我希望他们都去不同的学校。

不便也定义为:

  • 小学生 i 从家到学校的距离 E_i ,不便之处在于距离的总和,即 E_1 + E_2 + ... + E_N 。
  • 然而,立场 跳过 u 到位置 v 的距离是 它不能是 |u-v|

找出所有学生就读不同学校的情况下可能造成的不便最小化。

制約

  • 1 \leq N \leq 100000
  • 0 \leq A_i \leq 10^9
  • 0 \leq B_j \leq 10^9
  • A_1, A_2, \dots, A_N 不同
  • B_1, B_2, \dots, B_N 不同
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N

出力

请打印答案。 到达


入力例 1

1
869
120

出力例 1

749

小学生 1 的房子和小学 1 的距离是 给出 |869 - 120| = 749 。
在此输入中,小学生 1 必须是小学 1 ,因此该值是唯一可能带来的不便,并且是最小值。


入力例 2

6
8 6 9 1 2 0
1 5 7 2 3 9

出力例 2

5

小学生 1,2,3,4,5,6 如果您决定将它们发送至 3,2,6,4,5,1 ,将会带来不便 |8-7|+|6-5|+|9-9|+|1-2|+|2-3|+|0-1|=5 。 对于
由于我们无法进一步减少不便,所以答案是 5 。


入力例 3

10
31 41 59 26 53 58 97 93 23 84
17 32 5 8 7 56 88 77 29 35

出力例 3

211

入力例 4

20
804289382 846930886 681692776 714636914 957747792 424238335 719885386 649760491 596516649 189641420 25202361 350490026 783368690 102520058 44897761 967513925 365180539 540383425 304089172 303455735
35005211 521595368 294702567 726956428 336465782 861021530 278722862 233665123 145174065 468703135 101513928 801979801 315634021 635723058 369133068 125898166 59961392 89018454 628175011 656478041

出力例 4

2736647674