51nod 1091 线段的重叠

Posted by kele on July 15, 2018

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

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

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

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

#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;

}

不重叠的线段
ps:还试过二重循环计算,超时了,不放了