可乐的博客
0%

51nod 1091 线段的重叠

发表于 更新于
本文字数： 1.1k 阅读时长 ≈ 1 分钟

稍微有点难的贪心算法题目

最优子结构:
前n条线段重叠的最大距离=max(前n-1条线段的重叠的最大距离,第n条线段和前n-1条线段重叠的距离)

贪心选择:
计算第n条线段与前n-1条线段中的一条线段的重叠长度时，
test

\[重叠长度= \begin{cases} 另一条线段的终点-当前线段的起点,&if 当前线段终点大于另一条线段终点 \\ 当前线段终点-当前线段的起点,& if 当前线段终点小于另一条线段终点 \end{cases} \]

当前线段的终点我们没办法选择，但是我们可以选择另一条线段的终点，让它最大，所以我们可以维护一个最大的线段右端点(并不是最长线段的右端点)，也就是说和这条线段计算可以获得当前的最长重叠长度，也就是贪心选择性质

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
#include <iostream>
#include<algorithm>

using namespace std;

typedef struct line
{
    long long int start;
    long long int ends;
} line;



int cmp(line a,line b)
{
    if(a.start<b.start||(a.start==b.start&&a.ends>b.ends))
        return true;
    else
        return false;
}

int main()
{
    int n;
    cin>>n;
    line all[50005];
    for(int i=0; i<n; i++)
    {
        cin>>all[i].start>>all[i].ends;
    }
    long long int chongdie=0;
   // insert_sort(all,n);
    sort(all,all+n,cmp);
    long long int chongdie2=0;

    line m=all[0];
    for(int i=1;i<n;i++)
    {
        chongdie=max(chongdie,min(all[i].ends,m.ends)-all[i].start);
        if(all[i].ends>m.ends)
            m=all[i];
    }

    cout<<chongdie<<endl;

}

[不重叠的线段](/2018/07/15/51nod-1133/)
ps:还试过二重循环计算，超时了，不放了