易懂题解 | #多米诺骨牌#

将区间按照区间左端点排序, 贪心解决

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;

typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int N = 1e5 + 10, MOD = 998244353;
const int INF = 1e9;
const LL LL_INF = 1e18;
const LD EPS = 1e-8;

istream &operator>>(istream &is, i128 &val) {
    string str;
    is >> str;
    val = 0;
    bool flag = false;
    if (str[0] == '-') flag = true, str = str.substr(1);
    for (char &c: str) val = val * 10 + c - '0';
    if (flag) val = -val;
    return is;
}

ostream &operator<<(ostream &os, i128 val) {
    if (val < 0) os << "-", val = -val;
    if (val > 9) os << val / 10;
    os << static_cast<char>(val % 10 + '0');
    return os;
}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<PII> vec(n);
    for (int i = 0; i < n; ++i) cin >> vec[i].y;
    for (int i = 0; i < n; ++i) {
        cin >> vec[i].x;
        vec[i].y += vec[i].x;
    }

    sort(all(vec));

    vector<LL> cnt;
    int l = -INF, r = -INF;
    int t = 0;
    for (auto [x, y] : vec) {
        if (r >= x || l == -INF) {
            r = max(r, y);
            if (l == -INF) l = x;
            t++;
        }
        else {
            cnt.push_back(t);
            l = x, r = y;
            t = 1;
        }
    }

    if (l != -INF) cnt.push_back(t);
    sort(all(cnt), greater<LL>());
    LL ans = 0;
    for (int i = 0; i < min((int) cnt.size(), m); ++i) ans += cnt[i];
    cout << ans - 1 << '\n';
}

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

    int T;
    cin >> T;
    while (T--) solve();
    cout << fixed << setprecision(15);

    return 0;
}