【普及】后悔贪心

给你 $2$ 个长度为 $n$ 的数组 $[a_0, a_1, \cdots, a_{n-1}]$ 和 $[b_0, b_1, \cdots, b_{n-1}]$，你需要从这个 $2n$ 个数中选出 $n$ 个数，并满足如下 $2$ 个条件：

• 从数组 $a$ 中选 $m(0 \leq m \leq n)$ 个数，从数组 $b$ 中选 $n - m$ 个数
• 对于 $i(0 \leq i < n)$，满足 $a_i$ 和 $b_i$ 这两个数中有且仅有 $1$ 个被选中 你现在希望选出的 $n$ 个数和最大，输出这个最大的和

输入格式

第一行包含$n, m$

接下来 $n$ 行，每行包含 $2$ 个整数 $a_i$ 和 $b_i$

输出格式

输出选中的 $n$ 个数的最大和

4 2
1 2
3 5
6 9
10 14

27

提示

【样例 2 解释】

• 可以选中数组 $a$ 中的 $[1, 3]$，数组 $b$ 中的 $[9, 14]$

• 这样和为 $1+3+9+14=27$

• 这是一个经典问题，我们可以先不管数量限制，直接选 $a_i$ 和 $b_i$ 中较大的那个

• 然后再根据数量限制调整

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int n, m, x, y, ans = 0;
    cin >> n >> m;
    vector<priority_queue<int>> q(2);
    for (int i = 0; i < n; i++) {
        cin >> x >> y;
        // 先直接选大的, 把交换的差值放入 priority_queue
        if (x >= y) q[0].push(y - x), ans += x;
        else q[1].push(x - y), ans += y;
    }

    // 然后根据数量限制调整,  调整的时候贪心地选差值最小的即可
    while (q[0].size() > m) ans += q[0].top(), q[0].pop();
    while (q[1].size() > n - m) ans += q[1].top(), q[1].pop();
    cout << ans << '\n';

    return 0;
}

【数据范围】

• $\textstyle 1 \leq n \leq 10^5, 0 \leq m \leq n$
• $\textstyle 0 \leq a_i, b_i \leq 10^4$

来源