EOJ(排序)——15. Mr. Frog and big news

15. Mr. Frog and big news

作为一名资深记者，青蛙先生非常讨厌时不时蹦出来的大新闻。
偏偏最近大新闻还特别多。青蛙先生觉得应该做一点小小的贡献，把新闻的「雨声」尽可能地变得「小」一点。青蛙先生手上有 N 条国内新闻和 N 条国外新闻。这 N 条国内新闻的大小为 a1,a2…aN，N 条国外新闻的大小为 b1,b2…bN。他决定每天报道任意一条没有报道过的国内新闻和国外新闻。由于青蛙先生已经提前掌握了这 N 天的新闻，青蛙先生可以自己决定报道这些新闻的顺序。
某一天的新闻的大小由当天报道的国内新闻的大小 ai 和国外新闻 bi 决定。令 ci=(ai+bi)2，N 天新闻的大小是由 ∑i=1Nci 决定的。青蛙先生希望这个值最小化。
简单地说，就是给定两个数列 a1,a2…aN，b1,b2…bN，求 1 到 N 的两个全排列 s1,s2…sN，t1,t2…tN，使得 ∑i=1N(asi+bti)2 最小化。

输入

不超过 20 组数据，每组数据三行。
第一行是一个整数表示 N (1≤N≤2×105)。
第二行是 N 个整数，分别为 a1,a2…aN (−105≤ai≤105)。
第三行是 N 个整数，分别为 b1,b2…bN (−105≤bi≤105)。
处理到文件结束。

输出

每行一个最小值。

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

题目大意：

每组给出两个数组A[n]，B[n]，需要求A，B的排列，求每一项(A[i]+B[i])^2之和取得的最小值。

题目解析：

将A,B都按顺序排列，使A[i]依次与B[n-i-1]凑成一对。

具体代码：

#include<iostream>
#include<algorithm>
using namespace std;
long long A[200010],B[200010];
int main()
{
    int n;
    while(cin>>n){
    	long long sum=0;
    	for(int i=0;i<n;i++)
    		cin>>A[i];
		for(int i=0;i<n;i++)
    		cin>>B[i];
    	sort(A,A+n);
    	sort(B,B+n);
    	for(int i=0;i<n;i++){
    		sum+=(A[i]+B[n-i-1])*(A[i]+B[n-i-1]);
		}
		cout<<sum<<endl;
	}
    return 0;
}