B题是判断每两个区间的关系,而D是判断多个区间两两相交
注意到多个区间两两相交的充要条件是所有区间的交集不为空
所以沿用B的代码并且每次保留交集
只需要判断当前的区间是否和之前的交集是否相交,并且维护交集
就可以通过
#define l first
#define r second
void Refra1n()
{
ll n;cin>>n;
bool f=0;
vector<pair<ll,ll>>a(n+1);
for(ll i=1;i<=n;i++){
cin>>a[i].l>>a[i].r;
if(i==1)a[0]=a[i];
else {
if((a[0].l<a[i].l&&a[i].r<a[0].r)||(a[i].l<a[0].l&&a[0].r<a[i].r))f=1;
else if(a[i].l>a[0].r||a[i].r<a[0].l)f=1;
else {
if(a[i].l<a[0].l)a[0].r=a[i].r;
else a[0].l=a[i].l;
}
}
}
if(f)cout<<"No"<<endl;
else cout<<"Yes"<<endl;
}
全部评论
(0) 回帖