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

moziqian · 2025-02-14 18:46:24 · 题解

考虑贪心，将奇数存到一个数组里，再将偶数存到另一个数组里，然后分别排序，最后计算两个数组中前 k 大数的和中较大的那一个。

实现：

可以直接用数组，我用的是优先队列存。注意开 long long。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,k,a[100005],t1,t2,ans1,ans2;
priority_queue<int,vector<int>,less<int>> b,c;
bool cmp(int x,int y){return x>y;}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(register int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]&1)b.push(a[i]);
        else c.push(a[i]);
    }
    if(b.size()<k&&c.size()<k){
        cout<<0;
        return 0;
    }else{
        if(b.size()>=k){
            for(register int i=1;i<=k;i++){
                ans1+=b.top();
                b.pop();
            }
        }
        if(c.size()>=k){
            for(register int i=1;i<=k;i++){
                ans2+=c.top();
                c.pop();
            }
        }
        cout<<max(ans1,ans2);   
    }
    return 0;
}