51 Nod 1091 线段的重叠
2024-08-29 00:18:16
2017-09-24 19:51:41
writer:pprp
上一个题目就是关于线段重叠最大值,这个是找区间最长重合?
给你n个线段,然后让你在其中选择两条,使两条尽可能重合多一点
解决方法;
1、将所有线段进行排序,按照起点升序,终点降序的方法排序
2、找到一个对比区间,有两个操作
(1)如果区间在对比区间中,那么进行比较记录
(2)如果区间在对比区间之外,那么继续比较,并且更新对比区间,因为如果依然对比这个区间,相比当前的区间,原来的对比区间更加没有可能取得结果
代码如下:
#include <iostream>
#include <algorithm> using namespace std;
const int maxn = ; struct node
{
int l, r;
} pprp[maxn]; bool cmp(const node & n1, const node &n2)
{
if(n1.l < n2.l)
return true;
if(n1.l == n2.l && n1.r > n2.r)
return true;
return false;
} int main()
{
ios::sync_with_stdio(false);
int num;
cin >> num; for(int i = ; i < num ; i++)
{
cin >> pprp[i].l >> pprp[i].r;
} sort(pprp,pprp+num,cmp); node cp = pprp[];
int ans = -; for(int i = ; i < num ; i++)
{
if(cp.r >= pprp[i].r)
ans = max(ans,pprp[i].r-pprp[i].l);
else
{
ans = max(ans,cp.r-pprp[i].l);
cp = pprp[i];
}
} if(ans == -)
cout << "" << endl;
else
cout << ans << endl; return ;
}
最新文章
- 通过squid 禁止访问/只允许访问指定 网址
- JS中generater和箭头函数
- hdu 4597 + uva 10891(一类区间dp)
- CentOS6.5 mysql 5.5安装
- Multiple MySQL running but PID file could not be found
- Excel的一些常用设置
- 用手机地图GPS导航费流量吗?
- IIS 内部运行机制及Asp.Net执行过程详解
- ElasticSearch大批量数据入库
- REST总结
- Django用普通user对象登录的必须准备步骤
- [题解]ybt1365:FBI树(fbi)
- javaweb c3p0连接oracle12c
- sface
- [Shell]Shell调用并获取执行jar包后的返回值
- Java学习笔记之——内部类
- ionic3 点击input 弹出白色遮罩 遮挡上部内容
- 学习笔记TF023:下载、缓存、属性字典、惰性属性、覆盖数据流图、资源
- git branch 分支管理
- Linux学习之文件系统常用命令(七)