线段的重叠(贪心)

ゞ浴缸里的玫瑰 2022-05-15 03:12 252阅读 0赞

## 线段的重叠(贪心) ##

描述  
X轴上有N条线段，每条线段包括1个起点和终点。线段的重叠是这样来算的，\[10 20\]和\[12 25\]的重叠部分为\[12 20\]。  
给出N条线段的起点和终点，从中选出2条线段，这两条线段的重叠部分是最长的。输出这个最长的距离。如果没有重叠，输出0。  
输入  
第1行：线段的数量N(2 <= N <= 50000)。  
第2 - N + 1行：每行2个数，线段的起点和终点。(0 <= s , e <= 10^9)  
输出  
输出最长重复区间的长度。  
样例输入  
5  
1 5  
2 4  
2 8  
3 7  
7 9  
样例输出  
4  
分析：  
按照区间左端点升序排序,ans记录重叠的区间长度,另外用到了max min函数在c++中有定义就直接用了  
但是在Visual C++ 无法使用它们.  
下面是一段解释：

*标准库在<algorithm>头中定义了两个模板函数std::min() 和 std::max()。通常用它可以计算某个值对的最小值和最大值。
    可惜在 Visual C++ 无法使用它们，因为没有定义这些函数模板。原因是名字min和max与<windows.h>中传统的min/max宏定义有冲突。为了解决这个问题，Visual C++ 定义了另外两个功能相同的模板：_cpp_min() 和 _cpp_max()。我们可以用它们来代替std::min() 和 std::max()。
    为了禁用Visual C++中的 min/max宏定义，可以在包含<windows.h>头文件之前加上：
    #define NOMINMAX 
    或者将 NOMINMAX 加到 preprocessor difinitions 中。具体方法是：
    Visual C++ 6.0: 打开工程文件（*.dsw）或者（*.dsp），选中要定义的工程，进入菜单“Project”=>“Settings”（打开Settings对话框）=> 在左上角的“Setting for”下拉列表框处选择“All configurations”,然后选中“C/C++”标签=>在 “preprocessor difinitions”编辑框中加上“NOMINMAX”即可。
    Visual C++ 7.0: 打开工程项目文件（*.sln）或者（*.vcproj），选中要定义的工程项目，进入菜单“项目”=>“属性”（打开项目属性对话框）=>在左上角的“配置”下拉列表框处选择“所有配置”，然后在左边的“属性配置”中选择=>“C/C++”=>“预处理器”=>右边“预处理器定义”处加上“NOMINMAX”。*

代码总览：

/* 题意很简单，就是找两条线的重叠长度，然后依次更新找出最大值即可 。 把数据画画就出来了。 */ 
    
    #include<cstdio>
    #include<iostream>
    #include<algorithm>
    #define N 50005
    using namespace std;
    struct line {
        int s;
        int e;
    } a[N];
    
    int cmp(line x,line y) {
       //将线段按照 左端点从小到大排序，如果左端点相等，则右端点从小到大排序 
        if(x.s==y.s)
            return x.e <y.e;
        return x.s<y.s;
    }
    
    int main() {
        int n;
        while(cin>>n) {
            for(int i=0; i<n; i++)
                cin>>a[i].s>>a[i].e;
            //sort(a,a+n,cmp);
            int ans=0,sum,maxn=0,minn=0;//ans=0是为了没有重叠的时候好输出0，也便于后面的比较，
            //maxn minn记录处理每段线段得到的最左端和最右端，因为可能存在最大重叠部分不是相邻两条边。 
            for(int i=0; i<n; i++) {
                sum=min(maxn,a[i].e)-max(minn,a[i].s);//计算重叠部分 
                if(ans<sum)//更新最大重叠部分 
                    ans=sum; 
                maxn=max(maxn,a[i].e);//记录已经遍历过线段的最左端和最右端。 
                minn=min(minn,a[i].s);
            }
            cout<<ans<<endl;
        }
    }

//思路没有错 可是提交上去 PE~