51nod 1091线段的重叠--贪心

题意：x轴上有很多条线段，两个线段相交例如10 20和12 25相交，那么相交的长度就是20-12=8.有n条线段，选出两条重叠长度最长的。

条件：1重叠部分是两条线，最大的左端点和最小的右端点差值

思路：开始想复杂了，想到了扫描线，然后还用了set去解。其实贪心就可以了，以起点升序，终点降序排列，贪心取最大值。

代码:

1我最开始的想法，过的，我觉得也有一定的参考价值：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <list>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <set>
#include <algorithm>
using namespace std;
const int maxn=50005;
int ans;
struct node
{
    int x;
    int mak;
    int flag;
    bool operator<(const node &t)
    const
    {
        if(x==t.x)
            return flag>t.flag;
        return x<t.x;
    }
};
struct node num[maxn*2];
int vis[maxn][2];
int cir[maxn];
int main()
{
    int n;
    ans=0;
    scanf("%d",&n);
    memset(cir,0,sizeof(cir));
    for(int i=0; i<n; i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        vis[i][0]=x;
        vis[i][1]=y;
        num[i].x=x;
        num[i].flag=0;
        num[i].mak=i;
        num[i+n].x=y;
        num[i+n].flag=1;
        num[i+n].mak=i;
    }
    sort(num,num+2*n);
    set<int>s;
    s.insert(num[0].mak);
    int wordl=-1;
    for(int i=0; i<2*n; i++)
    {
        if(num[i].flag==0)
        {
            s.insert(num[i].mak);
        }
        else
        {
            s.erase(num[i].mak);
            set<int>::iterator ite;
            ite=s.find(wordl);
            int min1=-1;
            if(ite==s.end())
            {
                wordl=-1;
                for(ite=s.begin(); ite!=s.end(); ite++)
                {
                    if(min1==-1)
                    {
                        min1=vis[*ite][0];
                        wordl=*ite;
                    }
                    else
                    {
                        if(min1>vis[*ite][0])
                        {
                            min1=vis[*ite][0];
                            wordl=*ite;
                        }
                    }
                }
            }
            if(wordl==-1)
                continue;
            if(vis[num[i].mak][0]>=vis[wordl][0])
            {
                min1=vis[num[i].mak][1]-vis[num[i].mak][0];
            }
            else
            {
                min1=vis[num[i].mak][1]-vis[wordl][0];
            }
            if(ans<min1)
                ans=min1;
        }
    }
    printf("%d\n",ans);
    return 0;
}
           

2贪心：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <list>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <algorithm>
using namespace std;
struct node
{
    int x;
    int y;
    bool operator <(const node &t)//以起点为升序
    const
    {
        if(x==t.x)
        return y<t.y;
        return x<t.x;
    }
}num[50005];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&num[i].x,&num[i].y);
    }
    sort(num,num+n);
    int a=num[0].y;
    int max1=0;
    for(int i=0;i<n;i++)
    {
        max1=max(max1,min(a,num[i].y)-num[i].x);
        a=max(num[i].y,a);
    }
    printf("%d\n",max1);
    return 0;
}
           

总结：1贪心学习

          2对题目思考的不够透彻