A101793题解

$一.题意$

$给n个区间(奖励砖)和长度为d的特殊区间(弹球)，问使区间(奖励砖)中至少出现一次特殊区间的一部分(弹球)的特殊区间数量最小值$
$人话:我一次操作可以破坏长度为d的区间，求使所有奖励砖所在区间至少有一个地方被破坏的最小操作数$

$二.思路$

$我们看这题会觉得这题好像点覆盖线段的题目，但不同的是它是线段覆盖线段$
$那我们不妨把它转化为点覆盖线段$
$我们把k定义为以k为左端点的区间，那不就把线段转化成点了么$
$那对于我们任意一条区间[l_i,r_i]$
$可以转化为当k为左端点可以覆盖到这条区间时k的范围，就把线段覆盖线段转化为点覆盖线段了$
$也就是k+d-1\ge l_i且k\le r_i$
$解出来就是l_i-d+1\le k\le r_i$
$注意区间内不能出现负数$
$便转化为[max(l_i-d+1,1),r_i]$
$接下来就是点覆盖线段的模版$
$右端点排序->扫一遍并计数->输出$

$三.小练习$

#include <cstdlib>
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
struct node{
    long long l,r;
}b[200050];
long long n,k;
bool cmp(node a,node b){
    if (a.r!=b.r)return ①;
    return ②;
}
int main(){
    cin>>n>>k;
    for (int i=1;i<=n;i++){
        cin>>b[i].l>>b[i].r;
        b[i].l=max(③,b[i].l-k+1);
    }
    sort(④,cmp);
    long long lst=-1,ans=0;
    for (int i=1;i<=n;i++){
        long long l=b[i].l;
        long long r=b[i].r;
        if (⑤){
            lst=r;
            ans++;
        }
    }
    cout<<ans;
	return 0;
}

①
$A.$a.r<b.r
$B.$a.r>b.r
$C.$a.l<b.l
$D.$a.l>b.l
②
$A.$a.r<b.r
$B.$a.r>b.r
$C.$a.l<b.l
$D.$a.l>b.l
③
$A.$1
$B.$1ll
$C.$0
$D.$0ll
④
$A.$b+1,b+1+n
$B.$b,b+n
$C.$b+1,b+n
$D.$b,b+1+n
⑤
$A.$l<lst
$B.$l==lst
$C.$l!=lst
$D.$l>lst

$四.正解$

#include <cstdlib>
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
struct node{
    long long l,r;
}b[200050];
long long n,k;
bool cmp(node a,node b){
    if (a.r!=b.r)return a.r<b.r;
    return a.l<b.l;
}
int main(){
    cin>>n>>k;
    for (int i=1;i<=n;i++){
        cin>>b[i].l>>b[i].r;
        b[i].l=max(1ll,b[i].l-k+1);
    }
    sort(b+1,b+1+n,cmp);
    long long lst=-1,ans=0;
    for (int i=1;i<=n;i++){
        long long l=b[i].l;
        long long r=b[i].r;
        if (l>lst){
            lst=r;
            ans++;
        }
    }
    cout<<ans;
	return 0;
}

$时间复杂度在排序上O(nlogn)$
$参考答案:ACBAD$
$求点赞$