这是一条 关于贪心算法的题目。
重点是特殊点的判断问题,第一种是没有开始点,即没有开始点为1 的。第二种就是没有结束点,即没有终点为T 的。
显然这两种都是应该输入-1的。 然而还有另外一种情况,可以看一下 这种样例:
3 10
1 3
4 7
8 10
这样,显然也是应该输出-1 的。
将这三种情况判断到,然后就使用贪心。
用一个结构存储数据,一个before(b)一个end(e)。
然后排一下序,自己写一下cmp函数即可。
下面只要注意判断基本没问题。
最后 AC Memory: 876K Time: 63MS
附上代码。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int Max = 25000; int N, T; struct node { int b, e; }cows[25005]; bool cmp( const node & i1, const node & i2 ) { return i1.b < i2.b; } int main() { scanf( "%d%d", &N, &T ); for( int i = 0; i < N; ++ i ) { scanf( "%d%d", & cows[i].b, &cows[i].e ); } sort( cows, cows+N,cmp ); int num = 0; int right = 0; int top = 0; while( right < T ) { int begin = right + 1; for( int i = top; i < N; ++ i ) { if( cows[i].b <= begin &&cows[i].e >= begin ) { right = cows[i].e > right ? cows[i].e : right; } else if( cows[i].b > begin ) { top = i; break; } } if( begin > right ) break; else ++ num; } if( right != T ) num = -1; printf( "%d\n", num); return 0; }