一.题意一.题意一.题意
给n个区间(奖励砖)和长度为d的特殊区间(弹球)，问使区间(奖励砖)中至少出现一次特殊区间的一部分(弹球)的特殊区间数量最小值给n个区间(奖励砖)和长度为d的特殊区间(弹球)，问使区间(奖励砖)中至少出现一次特殊区间的一部分(弹球)的特殊区间数量最小值给n个区间(奖励砖)和长度为d的特殊区间(弹球)，问使区间(奖励砖)中至少出现一次特殊区间的一部分(弹球)的特殊区间数量最小值
人话:我一次操作可以破坏长度为d的区间，求使所有奖励砖所在区间至少有一个地方被破坏的最小操作数人话:我一次操作可以破坏长度为d的区间，求使所有奖励砖所在区间至少有一个地方被破坏的最小操作数人话:我一次操作可以破坏长度为d的区间，求使所有奖励砖所在区间至少有一个地方被破坏的最小操作数
二.思路二.思路二.思路
我们看这题会觉得这题好像点覆盖线段的题目，但不同的是它是线段覆盖线段我们看这题会觉得这题好像点覆盖线段的题目，但不同的是它是线段覆盖线段我们看这题会觉得这题好像点覆盖线段的题目，但不同的是它是线段覆盖线段
那我们不妨把它转化为点覆盖线段那我们不妨把它转化为点覆盖线段那我们不妨把它转化为点覆盖线段
我们把k定义为以k为左端点的区间，那不就把线段转化成点了么我们把k定义为以k为左端点的区间，那不就把线段转化成点了么我们把k定义为以k为左端点的区间，那不就把线段转化成点了么
那对于我们任意一条区间[li,ri]那对于我们任意一条区间[l_i,r_i]那对于我们任意一条区间[li ,ri ]
可以转化为当k为左端点可以覆盖到这条区间时k的范围，就把线段覆盖线段转化为点覆盖线段了可以转化为当k为左端点可以覆盖到这条区间时k的范围，就把线段覆盖线段转化为点覆盖线段了可以转化为当k为左端点可以覆盖到这条区间时k的范围，就把线段覆盖线段转化为点覆盖线段了
也就是k+d−1≥li且k≤ri也就是k+d-1\ge l_i且k\le r_i也就是k+d−1≥li 且k≤ri
解出来就是li−d+1≤k≤ri解出来就是l_i-d+1\le k\le r_i解出来就是li −d+1≤k≤ri
注意区间内不能出现负数注意区间内不能出现负数注意区间内不能出现负数
便转化为[max(li−d+1,1),ri]便转化为[max(l_i-d+1,1),r_i]便转化为[max(li −d+1,1),ri ]
接下来就是点覆盖线段的模版接下来就是点覆盖线段的模版接下来就是点覆盖线段的模版
右端点排序−>扫一遍并计数−>输出右端点排序->扫一遍并计数->输出右端点排序−>扫一遍并计数−>输出
三.小练习三.小练习三.小练习
①
A.A.A.a.r<b.r
B.B.B.a.r>b.r
C.C.C.a.l<b.l
D.D.D.a.l>b.l
②
A.A.A.a.r<b.r
B.B.B.a.r>b.r
C.C.C.a.l<b.l
D.D.D.a.l>b.l
③
A.A.A.1
B.B.B.1ll
C.C.C.0
D.D.D.0ll
④
A.A.A.b+1,b+1+n
B.B.B.b,b+n
C.C.C.b+1,b+n
D.D.D.b,b+1+n
⑤
A.A.A.l<lst
B.B.B.l==lst
C.C.C.l!=lst
D.D.D.l>lst
四.正解四.正解四.正解
时间复杂度在排序上O(nlogn)时间复杂度在排序上O(nlogn)时间复杂度在排序上O(nlogn)
参考答案:ACBAD参考答案:ACBAD参考答案:ACBAD
求点赞求点赞求点赞
