题解 | #小朋友做游戏#

这道题的代码来自出题人FriedChicken ，以此为基础进行学习这道题的思路以及代码处理，才用前缀和来计算孩子的幸福

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
typedef double db;
int T,A,B,n;
int va[10010],vb[10010];
bool cmp(int xx,int yy)
{
    return xx>yy;
}
int suma[10010],sumb[10010];
int main()
{
    cin>>T;
    while(T--)
    {
        cin>>A>>B>>n;//n是圆圈的总人数
        rep(i,1,A) scanf("%d",&va[i]);
        rep(i,1,B) scanf("%d",&vb[i]);
        int mxb=min(n/2,B);//n是总的所要的人数，b是闹腾孩子的总数
        //取最小的闹腾的人数为n/2，或者是B闹腾孩子人数本身
        if(mxb+A<n)//只能选闹腾的人数加全部幸福的人数不足所需要的人数的时候，无解
        {
            puts("-1");
            continue;
        }
        sort(va+1,va+1+A,cmp);//+1是因为上面从一开始的，va是从0开始的
        sort(vb+1,vb+1+B,cmp);//按照从大到小排序
        rep(i,1,A) suma[i]=suma[i-1]+va[i];//前缀和，用来计算幸福度
        rep(i,1,B) sumb[i]=sumb[i-1]+vb[i];
        int ans=-1;
        rep(ia,0,A)
        {
            int ib=n-ia;
            if(ib>mxb||ib<0) continue;
            ans=max(ans,suma[ia]+sumb[ib]);
        }
        printf("%d\n",ans);
    }
}