K番目の小数

1417 ワード

テスト:acdreamoj瑶瑶のK番目の大きさ
分治策は、シーケンス【L,R】を【】<=mid,【】>=mid,O(n)に分けていく.
int   x[5000008] ;

void  kthmin(int L , int R , int k){
      int i = L , j = R , mid = x[(L+R)>>1] ;
      do{
           while(x[i] < mid) i++ ;
           while(x[j] > mid) j-- ;
           if(i <= j){
                 swap(x[i] , x[j]) ;
                 i++ , j-- ;
           }
      }while(i <= j) ;
      if(L <= j && k <= j-L+1)  kthmin(L , j , k) ;
      if(i <= R && k >= i-L+1)  kthmin(i , R , k-(i-L)) ;
}

int  getint(){
     int t = 0 ;
     char c = getchar() ;
     while(c < '0' || c > '9')  c = getchar() ;
     while('0' <= c && c <= '9'){
          t = t*10 + c - '0' ;
          c = getchar() ;
     }
     return t ;
}

int main(){
    int   n , k  ;
    while(scanf("%d%d" , &n , &k) != EOF){
         for(int i = 1 ; i <= n ; i++)  x[i] = getint() ;
         kthmin(1 , n , n-k+1) ;
         printf("%d
" , x[n-k+1]) ; } return 0; }

第k小kthmin(1,n,k);
k番目のkthmin(1,n,n-k+1)