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

· · 题解

声明

由于本蒟蒻太蒟，所以只会使用暴力，不喜勿喷。

思路

由题可得因为选择卡牌如果奇偶性不同就会输出 0，所以我们要求最大值就要保证奇偶性相同。

那么我们在输入数据时可以分别用两个变量记录输入的奇数的总数和偶数的数量。

然后进行判断：

  1. 奇数总数和偶数都小于选择张数时，就必然打破奇偶相同的前提，所以只能输出 0。
  2. 奇数总数大于选择张数并且偶数总数小于选择张数时，易得选择奇数可得最大值。
  3. 偶数总数大于选择张数并且奇数总数小于选择张数时，易得选择偶数可得最大值。
  4. 奇数和偶数都大于选择张数时，易得选择奇数总值和偶数总值中更大的一方求最大值。

接着就是如何求最大得分的问题了，不难想到我们可以用两个数组分别存下奇数和偶数，用 sort 从小到大将奇数和偶数分别排列，计算最大值时从后向前累加选择张数个数即可。（当然也可以直接从大到小排列，从前到后累加，但蒟蒻忘了咋打代码了所以选择绕了一圈）。

最后在这里展出代码，马蜂不正不喜勿喷。

代码

#include <bits/stdc++.h>

using namespace std;
#define int long long//不开long long见祖宗

int n,k,cnt,res,ans,js,os;
int a[1000005],b[1000005],c[1000005];

signed main (){
    cin >> n >> k;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        if(a[i]%2==0){
            cnt++;//记录偶数数量
            b[cnt]=a[i];//存偶数
        }
        else if(a[i]%2!=0){
            res++;//记录奇数数量
            c[res]=a[i];//存奇数
        }
    }
    sort(b+1,b+1+cnt);//从小到大排序偶数
    sort(c+1,c+1+res);//从小到大排序奇数
    if(cnt>=k&&res>=k){
    int lk=k;
        for(int i=cnt; i>=1; i--){//从后向前累加
            if(k==0){
                break;
            }
            js+=b[i];
            k--;//每取一个数选择数量减一
        }
        k=lk;
        for(int i=res; i>=1; i--){
            if(k==0){
                break;
            }
            os+=c[i];
            k--;
        }//情况4
        ans=max(os,js);//取更大的一方
        cout << ans;
    }
    else if(cnt>=k&&res<k){
        for(int i=cnt; i>=1; i--){
            if(k==0){
                break;
            }
            js+=b[i];
            k--;
        }
        cout << js;
    }//情况3
    else if(cnt<k&&res>=k){
        for(int i=res; i>=1; i--){
            if(k==0){
                break;
            }
            os+=c[i];
            k--;
        }
        cout << os;
    }//情况2
    else{
        cout << 0;
    }//情况1

    return 0;//好习惯
}

提示

不开龙龙见祖宗！不开龙龙见祖宗！不开龙龙见祖宗！

重要的事情说三遍！