15. Mr. Frog and big news

单点时限: 2.0 sec

内存限制: 256 MB

本题时限为 2 秒。

作为一名资深记者,青蛙先生非常讨厌时不时蹦出来的大新闻。

偏偏最近大新闻还特别多。青蛙先生觉得应该做一点小小的贡献,把新闻的「雨声」尽可能地变得「小」一点。青蛙先生手上有 $N$ 条国内新闻和 $N$ 条国外新闻。这 $N$ 条国内新闻的大小为 $a_1, a_2 \ldots a_N$,$N$ 条国外新闻的大小为 $b_1, b_2 \ldots b_N$。他决定每天报道任意一条没有报道过的国内新闻和国外新闻。由于青蛙先生已经提前掌握了这 $N$ 天的新闻,青蛙先生可以自己决定报道这些新闻的顺序

某一天的新闻的大小由当天报道的国内新闻的大小 $a_i$ 和国外新闻 $b_i$ 决定。令 $c_i=(a_i+b_i)^2$,$N$ 天新闻的大小是由 $\sum\limits_{i=1}^{N} c_i$ 决定的。青蛙先生希望这个值最小化。

简单地说,就是给定两个数列 $a_1, a_2 \ldots a_N$,$b_1, b_2 \ldots b_N$,求 $1$ 到 $N$ 的两个全排列 $s_1, s_2 \ldots s_N$,$t_1, t_2 \ldots t_N$,使得 $\sum\limits_{i=1}^N{(a_{s_i}+b_{t_i})^2}$ 最小化。

输入格式

不超过 $20$ 组数据,每组数据三行。

第一行是一个整数表示 $N$ $(1 \leq N \leq 2 \times 10^5)$。

第二行是 $N$ 个整数,分别为 $a_1, a_2 \ldots a_N$ $(- 10^5 \leq a_i \leq 10^5)$。

第三行是 $N$ 个整数,分别为 $b_1, b_2 \ldots b_N$ $(- 10^5 \leq b_i \leq 10^5)$。

处理到文件结束。

输出格式

每行一个最小值。

样例

Input
3
1 3 2
-3 1 2
5
0 0 3 1 2
3 1 0 0 0
6
-1 -1 0 1 2 3
3 3 6 7 0 0
Output
18
24
99

76 人解决,77 人已尝试。

117 份提交通过,共有 255 份提交。

2.6 EMB 奖励。

创建: 3 年,3 月前.

修改: 2 年,6 月前.

最后提交: 20 小时前.

来源: 2017 CCCC 选拔

题目标签