题解：P11723 [JOIG 2025] カードゲーム 4 / Card Game 4

FDOI · 2025-02-14 15:48:03 · 题解

题意简述：

给定长度为 n 的数列 a，要求提取 k个数，若提取的数奇偶性相同，取其加和，否则答案为 0。

思路：

简单的贪心。

设置两个数组，分别记录数列中的奇数和偶数，并且记录个数，此时分为如下几种情况：

• 若奇数，偶数个数均小于 k，此时无论如何选取，答案均为 0。
• 若其中奇数或者偶数的个数小于 k，此时对于另一个数组进行排序，取其中最大的 k 个数。
• 否则，将两个数组均排序，并分别求最大的 k 个数，答案为二者最大值。

  代码实现：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k; 
int a[2000001],b[2000001],c[2000001];
signed main(){
    cin>>n>>k;
    int cnt1=0;
    int cnt2=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]%2==1) cnt1++,b[cnt1]=a[i]; //统计格式并记录。
        else cnt2++,c[cnt2]=a[i]; //同上。

    }
    if(k>cnt1&&k>cnt2){
        cout<<0<<endl;
    }
    else{
        int res1=0,res2=0;
        sort(b+1,b+cnt1+1); //排序
        reverse(b+1,b+cnt1+1); //反序
        for(int i=1;i<=k;i++){
            res1+=b[i]; //求和
        }
        sort(c+1,c+cnt2+1);
        reverse(c+1,c+cnt2+1);
        for(int i=1;i<=k;i++){
            res2+=c[i]; //求和
        }
        if(cnt1<k){ //判断情况
            cout<<res2;
        }
        else if(cnt2<k){
            cout<<res1;
        }
        else{
            cout<<max(res1,res2); //取最大值
        }
    }
    return 0;
}