[51nod] 1091 线段的重叠 贪心
2024-10-19 14:50:00
X轴上有N条线段,每条线段包括1个起点和终点。线段的重叠是这样来算的,[10 20]和[12 25]的重叠部分为[12 20]。
给出N条线段的起点和终点,从中选出2条线段,这两条线段的重叠部分是最长的。输出这个最长的距离。如果没有重叠,输出0。
Input
第1行:线段的数量N(2 <= N <= 50000)。
第2 - N + 1行:每行2个数,线段的起点和终点。(0 <= s , e <= 10^9)
Output
输出最长重复区间的长度。
Input示例
5
1 5
2 4
2 8
3 7
7 9
Output示例
4 贪心策略
按照起点升序排列,选择当前该区间的最长覆盖长度为min(end, L[i].e)-L[i].b, end为该区间之前最长的尾端点,则当前的最长覆盖长度为之前的最大值与选择该区间最大值中较大的一个,
最后一直维护最大值和最长尾端点即可。
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
#define LL long long
struct line
{
int b, e;
}L[];
int n; int cmp(line a, line b)
{
if (a.b != b.b)
return a.b < b.b;
else
return a.e < b.e;
} int main()
{
//freopen("1.txt", "r", stdin);
scanf("%d", &n);
for (int i = ; i < n; i++)
scanf("%d%d", &L[i].b, &L[i].e);
sort(L, L+n, cmp); int maxlen = , end = L[].e;
for (int i = ; i < n; i++) {
maxlen = max(maxlen, min(end, L[i].e)-L[i].b);
end = max(end, L[i].e);
}
printf("%d\n", maxlen); return ;
}
最新文章
- kafka的log存储解析——topic的分区partition分段segment以及索引等
- iphone状态栏高度?
- 手拼SQL小技巧,WHERE 1=1
- Codevs 1021 (玛丽卡)
- CCNA第四章第五章Cisco的IOS与SDM及其管理考试要点学习笔记
- git-svn
- Excel文件操作方式比较
- php socket编程参考资料
- STL中,迭代器的分类
- JavaScript之将JS代码放在什么位置最合适
- urllib2使用2
- 解决centos无法上传文件和打开文件夹
- 2.1Android界面View及ViewGroup(转)
- MongoDB入门命令
- zabbix-agent 启动不起来
- 阿里架构师带你深入浅出jvm
- UsernamePasswordAuthenticationToken
- BZOJ_3343_教主的魔法_分块+二分查找
- Hibernate-在Eclipse(Oxygen)中安装Hibernatetools插件
- c/c++ 数组 数组的引用,指针数组的引用
热门文章
- 我的Java开发学习之旅------>解惑Java进行三目运算时的自动类型转换
- Raspberry Pi3 ~ 使用eclipse进行远程调试
- Matlab图像处理(03)-基本概念
- ZOJ - 3430 Detect the Virus —— AC自动机、解码
- Storm worker 并行度等理解
- selenium 经常用到的API
- hdu-5778 abs(暴力枚举)
- homebrew cask安装launch rocket【转】
- bzoj2309 CTSC2011 字符串重排
- Codeforces Gym 101190 NEERC 16 G. Game on Graph(博弈+拓扑)