重庆网站建设有名 乐云践新,网站建设主要学什么,平面设计相关的网站有哪些内容,oa管理系统是什么题目描述 现给定n个闭区间[ai, bi]#xff0c;1in。这些区间的并可以表示为一些不相交的闭区间的并。你的任务就是在这些表示方式中找出包含最少区间的方案。你的输出应该按照区间的升序排列。这里如果说两个区间[a, b]和[c, d]是按照升序排列的#xff0c;那么我们有…题目描述 现给定n个闭区间[ai, bi]1in。这些区间的并可以表示为一些不相交的闭区间的并。你的任务就是在这些表示方式中找出包含最少区间的方案。你的输出应该按照区间的升序排列。这里如果说两个区间[a, b]和[c, d]是按照升序排列的那么我们有abcd。 请写一个程序 读入这些区间 计算满足给定条件的不相交闭区间 把这些区间按照升序输出。 输入输出格式 输入格式 第一行包含一个整数n3n50000为区间的数目。以下n行为对区间的描述第i行为对第i个区间的描述为两个整数1aibi1000000表示一个区间[ai, bi]。 输出格式 输出计算出来的不相交的区间。每一行都是对一个区间的描述包括两个用空格分开的整数为区间的上下界。你应该把区间按照升序排序。 输入输出样例 输入样例#1 复制 5
5 6
1 4
10 10
6 9
8 10输出样例#1 复制 1 4
5 10思路一开始看到题目还以为是用线段树毕竟省选题但仔细想了想用线段树的话好像很麻烦要维护不少信息呢况且数据范围1aibi1000000显然nlogn的算法无法承受。那么用什么做法呢我们可以发现n比较小只有5万那么我们可以考虑枚举区间。其实这题有一个类似于贪心的算法先按照左端点从小到大排序然后我们把区间看成是线段如果两条线段有交集那么我们可以视为把这两条线段合成为一条显然新线段的右端点即为两条线段中右端点较靠右的那一个。如果线段没有交集那么我们直接输出上一条线段的答案。这题这么水实在不像是省选原题啊233。 #includeiostream
#includecstdio
#includecstring
#includealgorithm
#includecmath
#includequeue
using namespace std;
const int maxn5e45;
int read()
{int ret0,f1;char cgetchar();while(c0||c9){if(c-) f-1;cgetchar();}while(c0c9){retret*10c-0;cgetchar();}return ret*f;
}
int n;
struct line{int l,r;
}e[maxn];
bool cmp(line A,line B)
{return A.lB.l;
}
int main()
{nread();for(int i1;in;i){e[i].lread(),e[i].rread();}sort(e1,e1n,cmp);int lle[1].l,rre[1].r;for(int i2;in;i){if(e[i].lrr) rrmax(rr,e[i].r);else{printf(%d %d\n,ll,rr);lle[i].l,rre[i].r;}}printf(%d %d\n,ll,rr);return 0;
} 转载于:https://www.cnblogs.com/loi-frank/p/7725808.html
