首页 > 代码库 > 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 }
View Code

 

POJ 1716