题解：AT_abc396_c [ABC396C] Buy Balls

yyycj · 2025-03-08 23:02:50 · 题解

题目传送门

题目简述

给定两个序列 B 和 W，从这两个序列里选任意个元素，但从 B 中挑选的元素数必须大于等于从 W 中挑选的元素数。求选择的数的总和的最大值。

主要思路

采用贪心的算法，维护两个自动从大到小排列 priority_queue，分别记录 B 和 W。

本题可以使用两个 while 循环来解决。由于从 B 中挑选的元素数必须大于等于从 W 中挑选的元素数，所以第一个循环里先同时从队列头获取元素。当满足以下两个条件时，就可以将答案增加两个队列头的和：

第二个循环第一个条件中已经提到过了，就是队列 B 剩下 \ge 0 的元素给答案加上。

AC Code

#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
typedef long double db;
const int INT_INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
// ----------------------------

// ----------------------------
priority_queue<int> q1, q2;
// ----------------------------

int main() {
    int n, m, b, w; cin >> n >> m;
    for (int _ = 1; _ <= n; _++) {
        cin >> b;
        q1.push(b);
    }
    for (int _ = 1; _ <= m; _++) {
        cin >> w;
        q2.push(w);
    }
    // ----------------------------
    ll ans = 0;
    while (!q1.empty() && !q2.empty()) {
        if (q2.top() >= 0 && q1.top() + q2.top() >= 0) {
            ans += q1.top() + q2.top();
            q1.pop();
            q2.pop();
        }
        else break;
    }
    while (!q1.empty() && q1.top() > 0) {
        ans += q1.top();
        q1.pop();
    }
    // ----------------------------
    cout << ans;
    return 0;
}