竞赛讨论区 > D题超ez解法
头像
_已被标记为牛弊_Refrain_Y
发布于 11-03 14:20 江西
+ 关注

D题超ez解法

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) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐