阶段 1：输入处理与数据预处理

  • 目标：读取输入数据，并将物体按位置排序，保证从左到右处理区间。
  • 操作：读取多组测试用例（T 组），每组先读物体数量 n、选取组数 m；按题目要求的输入顺序：先批量读取所有物体的高度 h，再批量读取所有物体的位置 x；将每个物体的 (x, h) 封装为结构体，按位置 x 升序排序（确保从左到右处理区间，避免漏判重叠）。

阶段 2：区间分组（核心逻辑）

  • 目标：将重叠 / 连续的物体归为一个 “组”，统计每个组的物体数量。
  • 核心规则：若物体 A 的覆盖区间[x_A, x_A+h_A]的右端点 ≥ 物体 B 的位置 x_B，则 A 和 B 属于同一组；
  • 操作：初始化：第一个物体为第一组，组内数量t=1，组的最远覆盖位置cmp = a[0].x + a[0].h；遍历所有物体（从第 1 个到第 n-1 个）：若当前组的最远覆盖位置cmp ≥ a[i+1].x：说明和下一个物体重叠，组数量t++，并更新组的最远覆盖位置为max(cmp, a[i+1].x + a[i+1].h)；若不重叠：当前组结束，将组数量t存入大顶堆，重置新组（t=1，cmp更新为下一个物体的覆盖右端点）；处理最后一组：遍历结束后，将最后一个组的数量t存入大顶堆（避免遗漏）。

阶段 3：选取最大 m 组求和

  • 目标：从所有组中选最大的 m 个组的数量求和，结果不超过总物体数 n。
  • 操作：利用大顶堆（priority_queue）的特性（堆顶始终是最大值），依次取出前 m 个最大值累加；若累加和 ≥ n，输出 n（因为总物体数只有 n）；否则输出累加和。
#include<bits/stdc++.h>
using namespace std;
using ll=long long;

struct p{
    ll x,h;
    // 排序规则：按物体位置x升序，保证从左到右处理区间
    bool operator<(const p&other)const{
        return x<other.x;
    }
};

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    ll T;
    cin>>T;
    while(T--){
        ll n,m;
        cin>>n>>m;
        vector<p>a(n);

        // ========== 阶段1：输入处理 ==========
        // 1.1 按题目要求读入所有物体的高度h
        for(ll i=0;i<n;i++){
            cin>>a[i].h;
        }
        // 1.2 按题目要求读入所有物体的位置x
        for(ll i=0;i<n;i++){
            cin>>a[i].x;
        }
        // 1.3 按位置x升序排序，保证从左到右处理区间
        sort(a.begin(),a.end());

        // ========== 阶段2：区间分组 ==========
        priority_queue<ll>q; // 大顶堆：存储每个组的物体数量，方便取最大值
        ll t=1; // 当前组的物体数量，初始为第一个物体
        ll cmp=a[0].x+a[0].h; // 当前组的最远覆盖位置（右端点）
        for(ll i=0;i<n;i++){
            // 2.1 处理最后一个物体：将最后一组存入堆
            if(i==n-1){
                q.push(t);
                break;
            }
            // 2.2 判定是否与下一个物体同组：当前组覆盖下一个物体的位置 → 同组
            if(cmp>=a[i+1].x){
                t++; // 组数量+1
                cmp=max(cmp,a[i+1].x+a[i+1].h); // 更新组的最远覆盖位置
            }else{
                // 2.3 不同组：当前组结束，存入堆，重置新组
                q.push(t);
                t=1;
                cmp=a[i+1].x+a[i+1].h;
            }
        }

        // ========== 阶段3：选取最大m组求和 ==========
        ll i=0,ans=0;
        // 取前m个最大的组数量累加
        while(!q.empty()&&i<m){
            ans+=q.top();
            q.pop();
            i++;
        }
        
        // 结果不超过总物体数n
        ans=min(ans,n);
        cout<<ans<<'\n';
    }
	return 0;
}