首页 > 代码库 > poj 1716 Integer Intervals
poj 1716 Integer Intervals
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.
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
43 62 40 24 7
Sample Output
4
以前做的是选一个点，这个题是选两个点，不过做法都一样，都是选区间最后两个点
#include<iostream>#include<cstdio>#include<map>#include<cstring>#include<string>#include<algorithm>#include<cmath>#include<vector>#include<set>using namespace std;const int maxn=10000+10;struct node{ int x,y;}a[maxn];bool vis[maxn];bool cmp(node xx,node yy){ return xx.y<yy.y;}int main(){ int n; while(scanf("%d",&n)!=EOF) { for (int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y); sort(a+1,a+n+1,cmp); memset(vis,0,sizeof(vis)); vis[a[1].y]=1; vis[a[1].y-1]=1; int ans=2; for (int i=2;i<=n;i++) { int m=0; for (int j=a[i].x;j<=a[i].y;j++) { if (vis[j]) m++; if (m==2) break; } if (m==0) { vis[a[i].y]=1; vis[a[i].y-1]=1; ans+=2; } if (m==1) { vis[a[i].y]=1; ans++; } } printf("%d\n",ans); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。