哈尔滨理工大学第八届程序设计团队赛K题

                     K.汪汪汪

Description

给n个区间[l, r],判断是否存在区间交叉。即是否存在1 <= i < j <= n,使得li < lj < ri < rj。

Input

多组数据

每组数据第一行一个整数n,第二行到第n + 1行每行两个数分别代表该区间的左右端点。

Output

如果存在交叉,输出“YES”;否则输出“NO”

Sample Input

2

1 3

2 4

3

1 7

2 4

5 6

Sample Output

YES

NO

Hint

1 <= n <= 1e5, 1 <= li < ri <= 2e5, 每组数据中所有的l,r互不相同。

所有组数据n的和不超过1e6.

读入数据较大,请使用高效的读入方式。

//套路题 之前做过两道类似的题目 一道叫“小琪画画” 一道叫“天神下凡” ,都是排序然后通过找一个圆的第一级祖先,

判断一些条件,出结果;

而这道题我的做法也是按照左端点从小到达,相等右端点从大到小排序,然后找左端点第一级祖先

像第二个样例,三个圆的第一级祖先分别为:0(祖先是平面),1(祖先是第一个圆),1

然后遍历每个圆 如果出现这个圆的右端点大于它第一级祖先的右端点说明 有交叉 跳出循环

代码如下:

    #include <iostream>
    #include <cstdio>
    #include <cstdio>
    #include <algorithm>

    using namespace std;

    const int maxn = 100005;
    const int inf = 0x7fffffff;
    struct node
    {
        int l,r;
    } a[maxn];

    int cmp(node A,node B)
    {
        if(A.l==B.l) return A.r>B.r;
        return A.l<B.l;
    }

    int main()
    {
        int n;
        while(scanf("%d",&n)!=EOF)
        {
            int flag = 0;
            for(int i=1; i<=n; i++)
            {
                scanf("%d %d",&a[i].l,&a[i].r);
            }

            sort(a+1,a+n+1,cmp);
            int s[maxn]= {
   0};
            int fa[maxn]={
   0};

            int top=0;
            for(int i=1; i<=n; i++)
            {
                while(top&&a[s[top]].r<=a[i].l)
                {
                    top--;
                }
                fa[i]=s[top];
                s[++top]=i;
            }
            a[0].r = inf;
            for(int i=2;i<=n;i++)
            {
                if(a[i].r>a[fa[i]].r)
                {
                    flag = 1;
                    break;
                }
            }
            if(flag)
            {
                printf("YES\n");
            }
            else
            {
                printf("NO\n");
            }
        }
        return 0;
    }

 

转载于:https://www.cnblogs.com/hao-tian/p/10092945.html

    原文作者:weixin_30361641
    原文地址: https://blog.csdn.net/weixin_30361641/article/details/98930370
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞