CSU->1971: 安排座位

NO IMAGE

1971: 安排座位

              Time Limit: 2 Sec     Memory Limit: 128 Mb      

Description

一年一度的暑期集訓又開始了!
作為老人的小明非常憂傷,因為他要給所有的新人安排座位。由於安排給新人的座位上的機器可能有各種毛病(比如很卡,上不了網之類的),這些問題的出現都會讓新人的訓練熱情下降。為了讓更多的新人能夠留下,小明自然希望大家的熱情都是高漲的。
對於每個新人,都會有一個熱情值ai,而每個座位都會有一個熱情耗損值bi,如果第i個新人坐在第j個位置,那這位同學對整個集訓隊熱情值的貢獻就是(ai – bj) ^2。現在給出所有新人的熱情值,所有位置的熱情耗損值,你能告訴小明採用最合理的位置安排方式後,能得到的最大的集訓隊熱情值是多少?
當然,每個位置只能坐一個新人,每個新人也必須坐在某個位置上

Input

第一行一個數字T表示資料組數
每組資料包括三行:
第一行為一個整數n,表示新人的人數
第二行為n個整數,第i個數字表示第i個同學的熱情值ai
第三行為n個整數,第i個數字表示第i個座位的熱情耗損值為bi
其中T<=10 , 0<=ai , bi <=100, 1<=n<=100000

Output

輸出一行只包含一個整數,表示集訓隊熱情值的最大值

Sample Input

2

3
2 5 1
0 0 1

3
2 5 1
3 2 5

Sample Output

29
26

Hint

Source

2017年7月月賽

題目連結:http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1971

題解:本題只需要對n個熱情值和n個熱情損耗值進行升序和降序的排列即可迅速得出答案,可以利用multiset容器的特點。

#include<iostream>
#include<set>
using namespace std;
int main(){
int T;
scanf("%d",&T);
int n;
multiset<int>m1;
multiset<int>m2;
int tmp,tmp2;
while(T--){
m1.clear();     //注意一定要清空容器 
m2.clear();
scanf("%d",&n);
int t=n;
while(t--){
scanf("%d",&tmp);
m1.insert(tmp);
}
t=n;
while(t--){
scanf("%d",&tmp2);
m2.insert(tmp2);
}
int sum=0;
multiset<int>::iterator it;
multiset<int>::iterator it2;
it=m1.begin();
it2=m2.end();
it2--;
t=n;
for(int i=0;i<n;i  ){
sum =((*it)-(*it2))*((*it)-(*it2));
it  ;
it2--;
}
printf("%d\n",sum);
}
return 0;
}