P2434 [SDOI2005]区间
2024-08-27 04:07:30
题目描述
现给定n个闭区间[ai, bi],1<=i<=n。这些区间的并可以表示为一些不相交的闭区间的并。你的任务就是在这些表示方式中找出包含最少区间的方案。你的输出应该按照区间的升序排列。这里如果说两个区间[a, b]和[c, d]是按照升序排列的,那么我们有a<=b<c<=d。
请写一个程序:
读入这些区间;
计算满足给定条件的不相交闭区间;
把这些区间按照升序输出。
输入输出格式
输入格式:
第一行包含一个整数n,3<=n<=50000,为区间的数目。以下n行为对区间的描述,第i行为对第i个区间的描述,为两个整数1<=ai<bi<=1000000,表示一个区间[ai, bi]。
输出格式:
输出计算出来的不相交的区间。每一行都是对一个区间的描述,包括两个用空格分开的整数,为区间的上下界。你应该把区间按照升序排序。
输入输出样例
输入样例#1: 复制
5
5 6
1 4
10 10
6 9
8 10
输出样例#1: 复制
1 4
5 10 差分
#include<bits/stdc++.h>
using namespace std;
#define For(i,a,b) for(int i=a;i<=b;i++)
#define FFor(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mod 100000000
#define maxn 1000005 int a[maxn],b[maxn];
int cnt=;
int n;
int x,y; int main()
{
cin>>n;
while(n--)
{
cin>>x>>y;
a[x]++;
b[y]++;
}
For(i,,maxn)
{
if(a[i]&&cnt==)cout<<i<<" ";
cnt+=a[i]-b[i];
if(b[i]&&cnt==)cout<<i<<endl;
} return ;
}
最新文章
- Spark运行模式与Standalone模式部署
- linux内核分析作业3:跟踪分析Linux内核的启动过程
- 【splay模板】
- Theme Section(KMP应用 HDU4763)
- 你必须了解的基础的 Linux 网络命令
- ajax读取文本内容(此处的txt文件和html文件处于同级目录)
- JMeter 测试Web登录
- CentOS 7.0安装MPlayer
- 多目标遗传算法 ------ NSGA-II (部分源码解析) 二进制编码的个体解码操作 decode.c
- Bootstrap 和 LESS
- mybatis随笔四之MapperProxy
- 调用Live555接收RTSP直播流,转换为Http Live Streaming(iOS直播)协议
- oracle查看锁和释放锁
- 【JS】数据类型
- ibatis的优缺点及可行性分析
- __x__(25)0907第四天__ overflow 父元素对溢出内容的处理
- 如何在网页中用echarts图表插件做出静态呈现效果
- BZOJ2428[HAOI2006]均分数据——模拟退火
- percona-5.7二进制多实例安装
- 潭州课堂25班:Ph201805201 django 项目 第二十八课 新闻elasticsearch搜索前后功台能实现 (课堂笔记)
热门文章
- react组件更新swiper
- web百度地图离线开发
- arcgis 加载高德地图 es6的方式
- ulimit命令&;pthread_create() error: Resource temporarily unavailable
- windows 删除删除不掉的文件
- 签署您的应用--手动签署 APK
- <;![CDATA[文本内容]]>;
- leetCode题解寻找最短字符路径
- unbind() 移除事件内处理方法
- Linux setenforce命令详解[SeLinux操作]