小朋友做游戏 （贪心双指针

添加链接描述
先讨论奇偶时是否可以选A成立
然后就是贪心双指针 先尽量选最大的
然后减去B不应该选的 最后加上A应该选的
要记得a b数组情况 否则影响贪心

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+9;
#define int long long
typedef long long ll;
int a[N],b[N],suma[N],sumb[N];
signed main(){
    int T;
    cin>>T;
    while(T--){
        int A,B,n,ans=0;
        cin>>A>>B>>n;
        memset(a,0,sizeof a);
        memset(b,0,sizeof b);
        for(int i=0;i<A;i++)scanf("%d",&a[i]);
        for(int i=0;i<B;i++)scanf("%d",&b[i]);
        sort(a,a+A,greater<int>());
        sort(b,b+B,greater<int>());
        if((n/2+1)>A&&(n%2)){//n为奇数  a不够选
            puts("-1");
            // cout<<"---"<<endl;
            continue;
        }
        else if((n%2==0)&&((n/2)>A)){
            puts("-1");
            continue;
        }
        if(n>A+B){
            puts("-1");
            continue;
        }   
            // int better=-1;
            // for(int i=0;i<min(A,B);i++){
            //     if(sumb[i]>suma[i]){
            //         better
            //     }
            // }

            // for(int i=0;i<min((n/2),B);i++)ans+=b[i];//尽量选b
            // n-=min((n/2),B);
            // if(n>A){
            //     puts("-1");
            //     continue;
            // }
            // for(int i=0;i<n;i++)ans+=a[i];
            // cout<<"---";
            int i=0,j=0;
            while((i<A||j<B)){
               if(i+j>=n)break;
                if(a[i]>=b[j]){
                    ans+=a[i];
                    i++;
                }
                else if(a[i]<b[j]){
                    ans+=b[j];
                    j++;
                }
            }
            int tot=0;
            // cout<<ans<<endl;
            // cout<<"///"<<i<<" "<<j<<endl;
           for(int k=(n/2);k<j;k++){
               ans-=b[k];
            //    cout<<k<<" "<<b[k]<<endl;
               tot++;
           }
           for(int k=i;k<min(A,n-(n/2));k++){
               tot--;
               ans+=a[k];
           }
        //    cout<<tot<<endl;
           
           if(tot!=0)puts("-1");
           else cout<<ans<<endl;
        
    }
    
    return 0;
}

最后

以上就是乐观黄蜂为你收集整理的小朋友做游戏 （贪心双指针的全部内容，希望文章能够帮你解决小朋友做游戏 （贪心双指针所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。