好贷网好贷款

poj1716 Integer Intervals(贪心)

发布时间:2016-12-5 2:19:45 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"poj1716 Integer Intervals(贪心)",主要涉及到poj1716 Integer Intervals(贪心)方面的内容,对于poj1716 Integer Intervals(贪心)感兴趣的同学可以参考一下。

Integer Intervals Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 12260   Accepted: 5178 Description An integer interval [a,b], a < b, is a set of all consecutive integers beginning with a and ending with b.  Write a program that: finds the minimal number of elements in a set containing at least two different integers from each interval. Input The first line of the input contains the number of intervals n, 1 <= n <= 10000. Each of the following n lines contains two integers a, b separated by a single space, 0 <= a < b <= 10000. They are the beginning and the end of an interval. Output Output the minimal number of elements in a set containing at least two different integers from each interval. Sample Input 4 3 6 2 4 0 2 4 7 Sample Output 4   题意: 给出n个int连续闭区间,求一点集元素的最小数目,该集合与各给出区间的交集至少含两元素 思路: 见代码 #include<stdio.h> #include<algorithm> using namespace std; struct ss { int a,b; } s[10004]; int cmp(ss x,ss y) { return x.b<y.b;//按右端点升序排列 } int main() { int n,i,ans,x1,x2; while(scanf("%d",&n)!=EOF) { for(i=0;i<n;i++) scanf("%d%d",&s[i].a,&s[i].b); sort(s,s+n,cmp); ans=2;//点集初始数目 x1=s[0].b-1; x2=s[0].b;//集合内初始元素 for(i=1;i<n;i++) { if(x2>=s[i].a&&x1<s[i].a) {//集合内仅有最新一个元素属于该区间 x1=x2; x2=s[i].b; ans++; } else if(x2<s[i].a) {//集合与该区间无交集 x1=s[i].b-1; x2=s[i].b; ans+=2; } } printf("%d\n",ans); } return 0; }  

上一篇:无题
下一篇:Java学习第14天:集合框架零接触和基本理解(List和Set)

相关文章

相关评论