题解 | 多米诺骨牌

#include <iostream>
#include <vector>
#include <array>
#include <queue>
#include <algorithm>
using namespace std;
using ll = long long;
void solve() {
    ll n, m;
    cin >> n >> m;
    vector<array<ll, 2>> nums(n, array<ll, 2> {});
    for (int i = 0; i < n; i++) {
        cin >> nums[i][1];
    }
    for (int i = 0; i < n; i++) {
        cin >> nums[i][0];
    }
    sort(nums.begin(), nums.end());
    priority_queue<int> pq;
    for (ll i = 0, cnt = 1, preMax = nums[0][0] + nums[0][1]; i < n; i++) {
        if (i == n - 1) {
            pq.push(cnt);
        } else if (preMax >= nums[i + 1][0]) {
            cnt++;
            preMax = max(preMax, nums[i + 1][0] + nums[i + 1][1]);
        } else {
            pq.push(cnt);
            preMax = nums[i + 1][0] + nums[i + 1][1];
            cnt = 1;
        }
    }
    ll t = min(static_cast<ll>(pq.size()), m);
    ll res = 0;
    // cout <<"pqsize() " << pq.size() << '\n';
    for (int i = 0; i < t; i++) {
        ll out = pq.top();
        pq.pop();
        // cout << "pq "<< out << " ";
        res += out;
    }
    // cout << '\n';
    cout << res << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
}
// 64 位输出请用 printf("%lld")