K番目の小数
1417 ワード
テスト:acdreamoj瑶瑶のK番目の大きさ
分治策は、シーケンス【L,R】を【】<=mid,【】>=mid,O(n)に分けていく.
第k小kthmin(1,n,k);
k番目のkthmin(1,n,n-k+1)
分治策は、シーケンス【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)