题解 | 多米诺骨牌

#include<bits/stdc++.h>
#define pii pair<int,int>

using namespace std;

const int N = 2e5+5;

int T;
int n,m;

struct node{
    int h;
    int x;
    bool operator<(const node& c)const{
        return x < c.x;
    }
}pos[N];

inline void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>pos[i].h;
    for(int i=1;i<=n;i++) cin>>pos[i].x;
    vector<int>v;
    sort(pos+1,pos+n+1);
    int l = 0, r= 0;
    int cnt = 0;
    for(int i=1;i<=n;i++){
        if(pos[i].x > r) {
        v.push_back(cnt);
        l = pos[i].x;
        r = pos[i].x + pos[i].h;
        cnt = 1;
        }
        else{
            r = max(r,pos[i].x + pos[i].h);
            cnt++;
        }
    }
    v.push_back(cnt);
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    int scnt = 0, ans = 0;
    for(int i:v){
        scnt++;
        ans += i;
        if(scnt == m) break;
    }
    //for(int i:v) cout<<i<<' ';
    cout<<ans<<'\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>T;
    while(T--) solve();
    return 0;
}