Advertisement
smatskevich

KStatistics

Oct 29th, 2016
312
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.45 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <assert.h>
  4. using std::cin;
  5. using std::cout;
  6. using std::vector;
  7.  
  8. // Разделение на две части по опорному. Возвращает позицию опорного элемента.
  9. int Partition( vector<int>& arr, int begin, int end )
  10. {
  11.     // Опорным считаем последний элемент массива.
  12.     int pivot = arr[end - 1];
  13.     int i = begin;
  14.     int j = end - 2;
  15.     while( i <= j ) {
  16.         for( ; arr[i] < pivot; ++i ) {} // Двигаем i вправо, за границу не выйдем, т.к. arr[end - 1] == pivot.
  17.         for( ; j >= begin && arr[j] >= pivot; --j ) {} // Двигаем j влево.
  18.         if( i < j ) {
  19.             std::swap( arr[i], arr[j] );
  20.         }
  21.     }
  22.     // Ставим опорный элемент на свое место.
  23.     std::swap( arr[i], arr[end - 1] );
  24.     return i;
  25. }
  26.  
  27. int KStatistics( vector<int>& arr, int k )
  28. {
  29.     assert( !arr.empty() );
  30.     int begin = 0;
  31.     int end = arr.size();
  32.     while( true ) {
  33.         int pivotPos = Partition( arr, begin, end );
  34.         if( pivotPos == k ) {
  35.             return arr[k];
  36.         }
  37.         if( pivotPos > k ) { // Нужная статистика в левой части.
  38.             end = pivotPos;
  39.         } else {
  40.             begin = pivotPos + 1;
  41.         }
  42.     }
  43. }
  44.  
  45. int main()
  46. {
  47.     int n = 0;
  48.     cin >> n;
  49.     int k = 0;
  50.     cin >> k;
  51.  
  52.     vector<int> arr( n, 0 );
  53.     for( int i = 0; i < n; ++i ) {
  54.         cin >> arr[i];
  55.     }
  56.  
  57.     cout << KStatistics( arr, k );
  58.     return 0;
  59. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement