本文主要是介绍CSU 1971: 安排座位,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
1971: 安排座位
Time Limit: 2 Sec Memory Limit: 128 Mb Submitted: 114 Solved: 83Description
一年一度的暑期集训又开始了!
作为老人的小明非常忧伤,因为他要给所有的新人安排座位。由于安排给新人的座位上的机器可能有各种毛病(比如很卡,上不了网之类的),这些问题的出现都会让新人的训练热情下降。为了让更多的新人能够留下,小明自然希望大家的热情都是高涨的。
对于每个新人,都会有一个热情值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
23 2 5 1 0 0 13 2 5 1 3 2 5
Sample Output
29 26
Hint
Source
2017年7月月赛
Author
简单贪心,可以把热情值从大到小排序,热情损耗值从小到大排序,用热情值大的去匹配损耗值小的,从而使得最后的热情值得到最大值
#include <iostream>
#include <cstring>
#include <stack>
#include <cstdio>
#include <cmath>
#include <queue>
#include <algorithm>
#include <vector>
#include <set>
#include <map>const double eps=1e-8;
const double PI=acos(-1.0);
using namespace std;
const int maxn=1e5+5;
int a[maxn],b[maxn];bool cmp(int a,int b){return a>b;
}int main()
{int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d",&a[i]);for(int j=0;j<n;j++)scanf("%d",&b[j]);sort(a,a+n,cmp);sort(b,b+n);double sum=0;for(int i=0;i<n;i++)sum+=(a[i]-b[i])*(a[i]-b[i]);printf("%.0f\n",sum);}return 0;
}/**********************************************************************Problem: 1971User: 201501080127Language: C++Result: ACTime:156 msMemory:2804 kb
**********************************************************************/
这篇关于CSU 1971: 安排座位的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!