题解 洛谷P2434 【[SDOI2005]区间】
2024-10-09 20:06:19
本题的贪心策略是以区间起点位置由小到大排序，然后开始合并。
区间按起点顺序由小到大排序，可以最大化合并成功的可能。
这个脑补应该不难想出来。（读者自证不难
直接上代码：
#include <bits/stdc++.h>
using namespace std;
struct interval
{
int start_,end_;
} a[50010];//定义一个结构体 方便排序
int n;
inline bool cmp(interval a,interval b)
{
return a.start_<b.start_;
}
int main()
{
cin>>n;
for(int i(1);i<=n;i++)
cin>>a[i].start_>>a[i].end_;
sort(a+1,a+1+n,cmp);//按照区间起点排序
int l,r;
l=a[1].start_;
r=a[1].end_;
int now(0);
while (++now<=n)
{
if(a[now].start_>r)//区间断开处理
{
cout<<l<<" "<<r<<endl;
l=a[now].start_;
r=a[now].end_>r?a[now].end_:r;
}
else r=max(a[now].end_,r);//没断开就维护一下 r
}
cout<<l<<" "<<r;//输出最后一组解
return 0;
}
最新文章
- spring的显示装配bean(1)------通过XML文件装配
- 设置float之后vertical-align失效
- Android自定义View滑动事件处理总结
- Recover Binary Search Tree [LeetCode]
- php--数据库三范式
- 【leetcode❤python】387. First Unique Character in a String
- EMVTag系列11《电子现金发卡行授权码》
- Implementation Documentation[转]
- android开发之socket快传文件以及消息返回
- 2013 Multi-University Training Contest 1 Cards
- 阿里开源Mysql分布式中间件：Cobar
- CentOS7 部署 tomcat
- PRINCE2重要性--光环国际培训
- Android笔记: fragment简单例子
- Java语法 示例
- spark-2.4.0-hadoop2.7-简单操作
- python,Day2，基础 2
- Ruby语法基础(三)
- Java面试题4
- jQuery操错题积累