链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
题目描述
牛牛是一个幼儿园老师，他经常带小朋友们一起做游戏。
现在，牛牛的班里有AAA个安静的小朋友和BBB个闹腾的小朋友，牛牛想要从中选出恰好nnn个人来做游戏。这个游戏需要小朋友们手拉手围成一个圆圈，但不妙的是，如果两个闹腾的小朋友在圆圈中紧挨着，他们就会打闹，导致游戏无法进行。
每个小朋友还有一个幸福度vvv，若这位小朋友被选中参加游戏，则会使得班级的幸福度增加vvv。
请你求出，在满足上述所有限制的情况下，恰当的安排围成圆圈的方法，能使得班级的幸福度最大为多少。
输入描述:
输入第一行是一个整数T(1≤T≤103)T(1\leq T\leq 10^3)T(1≤T≤103)，测试数据组数。
每组测试数据，第一行是三个整数A,B,n(2≤A,B≤104,3≤n≤A+B)A,B,n(2\leq A,B\leq 10^4, 3\leq n \leq A+B)A,B,n(2≤A,B≤104,3≤n≤A+B)，含义如题目所示。
第二行是AAA个数，第iii个数vai(1≤vai≤104)va_i(1\leq va_i \leq 10^4)vai(1≤vai≤104)表示某位安静小朋友的幸福度。
第三行是BBB个数，第iii个数vbi(1≤vbi≤104)vb_i(1\leq vb_i \leq 10^4)vbi(1≤vbi≤104)表示某位闹腾小朋友的幸福度。
此外，保证所有测试数据的(A+B)(A+B)(A+B)之和不会超过2∗1052*10^52∗105。
输出描述:
每组测试用例，输出一行一个整数，表示最大幸福度。若无论如何安排都不能进行游戏，输出−1-1−1。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,a,b,n;
ll a1[10005],b1[10005];
bool cmp(ll a,ll b){
return a>b;
}
int main()
{
cin>>t;
while(t--){
memset(a1,0,sizeof(a1));
memset(b1,0,sizeof(b1));
cin>>a>>b>>n;
ll p=(n+1)/2;
for(int i=0;i<a;i++){
cin>>a1[i];
}
for(int i=0;i<b;i++){
cin>>b1[i];
}
if(a<p){
cout<<-1<<endl;
}else{
sort(a1,a1+a,cmp);
sort(b1,b1+b,cmp);
ll sum=0;
for(int i=0;i<p;i++){
sum+=a1[i];
}
int cnt=p,ans=0;
for(int i=0;i<n-p;i++){
if(a1[cnt]>=b1[ans] && cnt<a){
sum+=a1[cnt++];
}else if(a1[cnt]<b1[ans] && ans<b){
sum+=b1[ans++];
}else if(cnt>=a){
sum+=b1[ans++];
}else if(ans>=b){
sum+=a1[cnt++];
}
}
cout<<sum<<endl;
}
}
return 0;
}
