#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,INF=0x3f3f3f3f;
int st,ed,n;
struct Range{
int l,r;
bool operator < (const Range &W) const{
return l< W.l;
}
}range[N];
int main(){
scanf("%d%d",&st,&ed);
scanf("%d",&n);
for(int i=0;i<n;i++){
int a,b;
scanf("%d%d",&a,&b);
range[i]={a,b};
}
sort(range,range+n);
bool flag=false; //判断是否成功,初值为失败
int res=0;
for(int i=0;i<n;i++){
int j=i,r=-INF;
//如果每次不把r更新为-2e9的话,st和r相等,可能不会出现r<st的情况,如果无法覆盖的话,就会一直循环
while(j<n&&range[j].l<=st){ //双指针算法来更新左端点小于st的线段中,能够到大的最远位置
r=max(r,range[j].r);
j++;
}
if(r<st){ //当前右端点的最远位置不能到达下一线段的左端点,一定不能覆盖
res=-1;
break;
}
res++;
if(r>=ed){
flag=true; //只有从这个出口出去才被视作成功覆盖
break;
}
st=r; //更新下一次的st,i
i=j-1;
}
if(flag) cout<<res<<endl;
else cout<<-1<<endl;
}
问个问题,就是每次选出r之后,我的st为什么要变成r,而不是r+1呢?
我的想法是:选出r就说明到r的我已经覆盖了,剩下的就是r +1到ed需要覆盖了,那为什么不将我的st变成r+1呢?
比如 当前覆盖到了3 如果你从r + 1开始,那3 ~ 4 这个区间谁来覆盖?
这个区间是连续的,不是离散的
原来如此,感谢🙏
为什么i = j-1
因为i要从选中的j区间的下一个区间开始枚举,且上面选中j区间后j进行了j操作,就表示了j的下一个区间。又因为有i,就又多加了一次,所以j要减一。
j加一和i加一
hhh,六个月之后的回复
不要也能AC,不过时间差了10倍。
比如第一次时,while遍历所有的左端点比st小的区间,此时答案应该为j-1,比如答案为j=4时,但j=4这个区间我没用,所以我要i=j-1
时隔一年的回复
“可能不会出现r<st的情况”,请问能否举例呢?
因为上一时刻st = r,某时刻的r = 10,这时的st = 10; 然后,如果接下来的区间是[1, 2], [1,3], [2,5]这样的右区间小于10的这种区间,那么while()循环之后r还是等于st,本应该跳出循环,但是r < st就不成立,后面会死循环。总而言之,r代表的是[1, 2], [1,3], [2,5]这样左端点小于st的右端点的最大值,而不能直接给st一个大值,比[1, 2], [1,3], [2,5]所有右端点都大的值,那这样的r还有什么意义呢?
为什么i = j-1啊 是因为 for的i++么?
你是对的,这里i = j-1,只是因为 i。 你可以 让i = j, 然后删掉for定义里的i。一样可以ac
确实j-1是因为i++,但为什么呢?
已经判断flag的状态了,为什么还要给res赋值-1呢
这个代码不是WA了么
之前的代码被新加的数据hack了,已更新
具体的bug为如果for循环遍历完所有的线段并没有完全覆盖ed(线段右端点),也会被视为成功
增加了flag作为判别是否成功的依据,即可解决