首页 > 代码库 > POJ 1716
POJ 1716
题意:在几个区间里面,挑选出几个数字组成一个集合,使得每个区间都至少有两个数字在这个集合里面,求这个集合的最少数字个数。
题解:贪心法,先对区间排序下,以右端点排序,把每个区间扫一遍过去,看区间内有几个元素在当前集合中。
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cmath> 5 #include <cctype> 6 #include <time.h> 7 #include <string> 8 #include <set> 9 #include <map>10 #include <queue>11 #include <vector>12 #include <stack>13 #include <algorithm>14 #include <iostream>15 using namespace std;16 #define PI acos( -1.0 )17 typedef long long ll;18 typedef pair<int,int> P;19 const double E = 1e-8;20 21 const int NO = 10000 + 5;22 int a[NO<<1];23 int n;24 struct ND25 {26 int start, en;27 }st[NO];28 29 bool cmp( const ND &a, const ND &b )30 {31 return a.en < b.en;32 }33 34 int main()35 {36 while( ~scanf( "%d",&n ) )37 {38 for( int i = 0; i < n; ++i )39 scanf( "%d%d", &st[i].start, &st[i].en );40 sort( st, st+n, cmp );41 int cur = 0;42 a[cur++] = st[0].en-1;43 a[cur++] = st[0].en;44 for( int i = 1; i < n; ++i )45 {46 int num = 0;47 for( int j = 0; j < cur; ++j )48 if( st[i].start <= a[j] && st[i].en >= a[j] )49 {50 ++num;51 if( num >= 2 )52 break;53 }54 if( num == 0 )55 {56 a[cur++] = st[i].en-1;57 a[cur++] = st[i].en;58 }59 if( num == 1 )60 a[cur++] = st[i].en;61 }62 printf( "%d\n", cur );63 }64 return 0;65 }
POJ 1716
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。