allia

катый элемент 51 (страшно но работает)

Oct 18th, 2020 (edited)
619
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cmath>
  3. #include <stdio.h>
  4. using namespace std;
  5.  
  6. void sift (int *arr, int first, int last)
  7.  
  8.  {
  9.   int j = first;
  10.   int k = first*2+1;
  11.  
  12.   while (k <= last)
  13.   {
  14.     if (k < last && arr[k] < arr[k+1])
  15.      k++; // больший сын
  16.      if (arr[j] < arr[k])
  17.      {
  18.         swap(arr[j], arr[k]);
  19.          j = k;
  20.          k = k*2+1;
  21.      }
  22.    else break;
  23.  }
  24. }
  25.  
  26. void sort (int *arr, int razmer)
  27. {
  28.   for (int i = razmer/2; i >= 0; i--)
  29.    sift (arr, i, razmer-1);
  30.  
  31.  for (int m = razmer-1; m >= 1; m--)
  32.  {
  33.    swap(arr[0], arr[m]);
  34.    sift (arr, 0, m-1);
  35.  }
  36. }
  37.  
  38. int main()
  39. {
  40.   int n = 0, k = 0, znach = 0, index = 0, shet = 0, x=1, shetchik = 0;
  41.  
  42.   scanf("%d", &n);
  43.   scanf("%d", &k);
  44.  
  45.   int *result = new int[k];
  46.  
  47.   scanf("%d", &znach);
  48.   result[0] = znach;
  49.  
  50.   while(x != k) // избегаем повтора и ситуации к=3, все к элементы максимальны
  51.    {
  52.     scanf("%d", &znach);
  53.     shetchik++;
  54.     if (znach != result[x-1])
  55.     result[x++] = znach;
  56.   }
  57.    
  58.   sort(result, k); // сортируем
  59.  
  60.  if (shetchik < n-1) // если в массиве есть элементы, которых нет в резалте
  61.  for (int i = x; i < n; i++)
  62.   {
  63.    scanf("%d", &znach); // вводим значение
  64.  
  65.     while (index < k && znach > result[index]) /* пока мы не за границами и введенное знаечение больше элементов резалта */
  66.        {
  67.          index++;
  68.          shet++;
  69.        }
  70.  
  71.     if (shet!=0 && result[index-1] != znach) /* если мы заходили в цикл уайл и такого элемента еще не было в резалте вставляем элемент в резалт и сдвигаем все элементы до него, меньший вылетает*/
  72.          {
  73.           for (int j=0; j < index-1; j++)
  74.             result[j] = result[j+1];
  75.           result[index-1] = znach;
  76.          }
  77.          
  78.       index = 0;
  79.       shet = 0;
  80.   }
  81.  
  82. printf ("%d", result[0]);// выводим необходимый элемент
  83. }
RAW Paste Data