官方题解

NoonMaple

2026-01-26 09:38:18

发布于：浙江

11阅读

0回复

0点赞

题目大意

给定 $n$ 行砖块，每行向右无限延伸并且有且有一段连续的区间为奖励砖，每次可以选择一个区间长度 $d$ ，并且将这 $d$ 列每行所有的砖块都破坏，奖励砖只要被破坏一个格子就会被全部破坏，求将所有奖励砖都破坏需要的最少操作次数。

解题思路

这是一道经典的贪心问题，在排序时我们会想到，如果破坏一个奖励砖的最右端，那么就会破坏更多的奖励砖，所以我们按照右端点排序，模拟每次打破当前剩余第一个奖励砖的最右端即可。

参考答案

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;

struct P{
    int l,r;
}p[N];

bool cmp(P a, P b){
    return a.r<b.r;
}

int main(){
    int n,d;cin>>n>>d;
    for(int i=1;i<=n;i++) cin>>p[i].l>>p[i].r;
    sort(p+1,p+n+1,cmp);

    int now=0;
    int res=0;
    for(int i=1;i<=n;i++){
        if(p[i].l>now){
            res++;
            now=p[i].r+d-1;
        }
    }
    cout<<res<<endl;
    return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 1

Zzzzzzsr（不处）

不理解，为什么不能按左端点升序排，一样再按右端点降序排，这样从第一块的右端点开始打，贪心覆盖。

然后被hack了，至今未想到hack

昨天来自广东

Zzzzzzsr（不处）

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,d;
struct node{
    int l,r;
};
node a[200009];
bool cmp(node x,node y){return x.l == y.l?x.r<y.r:x.l<y.l;}
signed main(){
    cin>>n>>d;
    for(int i = 1;i<=n;++i){
        cin>>a[i].l>>a[i].r;
    }
    sort(a+1,a+n+1,cmp);
    int cnt = 1,mx = a[1].r+d-1;
    for(int i = 2;i<=n;++i){
        if(a[i].l<=mx) continue;
        cnt++;
        mx = a[i].r+d-1;
    }
    cout<<cnt;
}

昨天来自广东