题解 | 多米诺骨牌

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
pair<int,int> gu[N];
int n,m;

signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            cin>>gu[i].second;
        }
        for(int i=1;i<=n;i++)
        {
            cin>>gu[i].first;
        }
        sort(gu+1,gu+1+n);
        // for(int i=1;i<=n;i++)
        // {
        //     cout<<gu[i].first<<' '<<gu[i].second<<' ';
        // }
        // cout<<endl;
	  //维持一个最大连锁区段，左边界为l，右边界为r，区段内总骨牌数为num
        int l=gu[1].first,r=gu[1].second+gu[1].first;
        int num=1;
        vector<int> res;
        for(int i=2;i<=n;i++)
        {
            if(gu[i].first>r)
            {
                l=gu[i].first;
                r=gu[i].second+gu[i].first;
                res.push_back(num);
                num=1;
            }
            else
            {
                r=max(r,gu[i].first+gu[i].second);
                num++;
            }
            
        }
        res.push_back(num);
        sort(res.begin(),res.end());
        int ssum=0;
        // for(int i=0;i<res.size();i++)
        // {
        //     cout<<res[i]<<' ';
        // }
        // cout<<endl;
        while(m--&&res.size())
        {
            ssum+=res[res.size()-1];
            res.pop_back();
        }
        cout<<ssum<<'\n';
    }
    return 0;
}