xfstart07
Get busy living or get busy dying

文章


#include < iostream >
using   namespace  std;
int  n;
int  size;
int  c[ 10001 ];
int  f[ 10001 ];
int  a[ 10001 ];
int  bsearch( int  ai)
{
        
int  l = 1 ,r = size;
        
while (l <= r)
        {
                
int  mid = (l + r) >> 1 ;
                
if (ai > c[mid - 1 ] && ai <= c[mid])  return  mid;
                
else   if (ai > c[mid]) l = mid + 1 ;
                
else  r = mid - 1 ;
        }
}
int  main()
{
        scanf(
" %d " , & n);
        
for ( int  i = 1 ;i <= n; ++ i) scanf( " %d " , & a[i]);
        c[
1 ] = a[ 1 ]; f[ 1 ] = 1 ; size = 1 ;
        
for ( int  i = 2 ;i <= n; ++ i)
        {
                
int  j;
                
if (a[i] <= c[ 1 ]) j = 1 ;
                
else   if (a[i] > c[size]) j =++ size;
                
else  j = bsearch(a[i]);
                c[j]
= a[i]; f[i] = j;
        }
        printf(
" %d\n " ,size);
        
return   0 ;
}





posted on 2009-04-18 16:02 xfstart07 阅读(287) 评论(0)  编辑 收藏 引用 所属分类: 代码库

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