HDU 2037 今年暑假AC 赤裸裸的贪心

时间：2011-04-11 来源：Lvsi

这道题是一道赤裸裸的贪心题,在这以前我只是看了贪心的思想,还没实现过,今天看了别人这道题代码才知道AC的代码原来是这样写的,小小水一下;

这是一道典型的贪心算法,只要每一步都选占用时间最小的同时要使剩余时间最大的,也就是说,没一会你都要找一个结束最早的.当你找到第一个后,一定要使剩余的时间最长,以后每选一个都要考虑这个问题,这样你每一步都最优的话,结果也是最优的;

具体做法就是先按结束的时间进行排序,然后每次取最小的,但是要保证和前面取的那个没有冲突

#include<stdio.h>
#include<stdlib.h> 
struct r
{
       int s,e; 
}act[124];
int n,count;
int cmp( const void *a , const void *b )
{
    return ( ( r * ) a ) -> e - ( ( r * ) b ) ->e; 
} 
int main( )
{
    while( scanf( "%d",&n ),n )
    {
           for( int i = 0; i < n; ++i )
                scanf( "%d%d",&act[i].s,&act[i].e );
           qsort( act,n,sizeof( act[0] ),cmp );
           for( int  i = count = 1,k = 0; i < n; ++i )
                if( act[i].s >= act[k].e )
                {
                    ++count;
                    k = i; 
                    }
           printf( "%d\n",count ); 
           } 
    return 0; 
}

相关阅读更多 +