题解 | 多米诺骨牌

注意到，骨牌倒塌是连锁的，（我们要先将x从小到大排序）就是说，如果当前骨牌把下一个骨牌推倒，如果当前骨牌的高度不足以推倒下下一个骨牌，但是已经被推倒的下一个骨牌的高度可以推倒下下一个骨牌，那下下一个骨牌就是可以推倒的。那么我们只需要维护当前推倒骨牌中的最大高度（cur），如果能推倒当前连锁数（cnt+1），以此类推，如果cur不足以推倒下个骨牌，那我们就要新推倒一个作为开头，cur=新开的x+这个x的h，我们还需要把上个连锁序列能推倒的数量记录到序列res中(尾插到res中)，然后我们将cnt=1，大致流程就是这样，然后将res系列从小到大排序，然后如果m大于res序列的长度，说明能将n个骨牌全部推倒，ans=n，反之就遍历res前m个数，ans求和，输出即可，代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define debug(x) cerr << #x << ": " << x << '\n';
const int INF = 0x3f3f3f3f3f3f3f3f;
//倒序不要忘记是--不是++
void solve(){
    int n,m;cin>>n>>m;
    vector<pair<int,int>> a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i].second;
    for(int i=1;i<=n;i++) cin>>a[i].first;
    sort(a.begin()+1,a.end());
    vector<int> res;
    int cur=a[1].first+a[1].second,cnt=1;
    for(int i=2;i<=n;i++){
        auto [x,h]=a[i];
        if(cur<x){
            cur=x+h;
            res.push_back(cnt);
            cnt=1;
        }
        else{
            cnt++;
            cur=max(cur,x+h);
        }
    }
    res.push_back(cnt);
    sort(res.begin(),res.end(),greater<int>());
    int ans=0;
    if(m>=res.size()) ans=n;
    else{
        for(int i=0;i<m;i++) ans+=res[i];
    }
    cout<<ans<<"\n";
}
signed main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t = 1;
    cin>>t;
    while(t--){
        solve();
    }return 0;
}