线段的重叠(贪心) ゞ 浴缸里的玫瑰 2022-05-15 03:12 204阅读 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~
还没有评论，来说两句吧...