51nod 1091线段的覆盖

发表于 | 更新于 | 阅读次数：

题目链接

将所有线段按照起点从小到大排序，起点相同的，按终点从大到小排序。这一题里，两条线段之间的关系可分为三种：不相交，相交，覆盖。下面重点来了，设有三条线段a，b，c，按上述顺序排列，当a与b相交但是不覆盖的时候，bc的重叠部分一定大于等于ac重叠部分，想明白这一点后，问题就解决了。

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <algorithm>
#include <stdlib.h>
using namespace std;
struct node
{
    int be, en;
};
node a[50000];
int cmp(node x, node y)
{
    if (x.be == y.be)
        return x.en > y.en;
    return x.be < y.be;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i].be >> a[i].en;
    }
    sort(a, a + n, cmp);
    int ans = 0;
    node zan = a[0];
    for (int i = 1; i < n; i++)
    {
        if (a[i].be < zan.en)//相交
        {
            if (a[i].en <= zan.en && a[i].be >= zan.be)//覆盖
            {
               ans=max(ans,a[i].en-a[i].be) ;
            }
            else
            {
                ans=max(min(a[i].en,zan.en)-a[i].be,ans);//相交但不覆盖
                zan = a[i];
            }
        }
        else 
        {
            zan=a[i];
        }
    }
    cout << ans << '\n';

    return 0;
}
0%