Pku 1032 Parliament
#include  < stdio.h >

int  result[ 500 ];

 int  main()
 {
     int  n;
    
     while ( scanf( " %d " , & n) !=  EOF )
     {
         int  sum =   0 ;
         int  len =   0 ;
         int  value =   2 ;
        
         while (  true  ) {
            sum +=  value;
            result[len ++ ] =  value ++ ;
             if ( sum +  value >  n )  break ;
        }
        value -- ;
         int  left =  n -  sum;
         if ( value ==  left )
         {
             for (  int  i =   0 ; i <  len;  ++ i ) result[i] ++ ;
            result[len - 1 ] ++ ;
        }
         else   for (  int  i =  len -   1 ; i >=   0 , left >   0 ; i -- , left --  ) result[i] ++ ;
        
         for (  int  i =   0 ; i <  len;  ++ i ) 
         {
             if ( i ==   0  ) printf( " %d " , result[i] );
             else         printf( "  %d " , result[i] );
        }
        printf( " \n " );
    }
    
     return   0 ;
}

做法就是求出以2起始的最大连续自然数序列之和sum，使得sum的值不超过输入数n，
然后分情况讨论：

设此最大序列为2、3、……、w，则：

1。若剩余值（n-sum）等于w，则最后输出序列为：3、4、……、w、w+2，即将原最大序列每项加1，再将最后剩余的一个1加到最后一项上。

2。若剩余值（n-sum）小于w，则从序列的最大项i开始，从大到小依次将每项加1，直到剩余值用完。

posted on 2008-10-29 10:26 Darren 阅读(485) 评论(0)  编辑 收藏 引用 所属分类: 动态规划

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 Darren