daily pastebin goal
70%
SHARE
TWEET

Untitled

a guest Jan 14th, 2018 50 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include<math.h>
  3. using namespace std;
  4.  
  5. void siftDown(int *a, int i, int n, int k)
  6. {
  7.     int j, m;
  8.     m = a[i];
  9.     j = 2 * i;
  10.     while (j <= n)
  11.     {
  12.         if (j < n && a[j + 1] > a[j])
  13.             j = j + 1;
  14.         if (m > a[j])
  15.             break;
  16.         else if (m <= a[j])
  17.         {
  18.             a[j / 2] = a[j];
  19.             j = 2 * j;
  20.         }
  21.     }
  22.     a[j / 2] = m;
  23.     return;
  24. }
  25. void siftDown1(int *a, int i, int n, int k)
  26. {
  27.     int j, m;
  28.     m = a[i];
  29.     j = 2 * i;
  30.     while (j <= n)
  31.     {
  32.         if (j < n && a[j + 1] < a[j])
  33.             j = j + 1;
  34.         if (m < a[j])
  35.             break;
  36.         else if (m >= a[j])
  37.         {
  38.             a[j / 2] = a[j];
  39.             j = 2 * j;
  40.         }
  41.     }
  42.     a[j / 2] = m;
  43.     return;
  44. }
  45. void heapsort(int *a, int n, int k)
  46. {
  47.     int i, temp;
  48.     for (i = n; i >= n - k; i--)
  49.     {
  50.         temp = a[i];
  51.         a[i] = a[1];
  52.         a[1] = temp;
  53.         siftDown(a, 1, i - 1, k);
  54.     }
  55. }
  56.  
  57. void heapsort1(int *a, int n, int k)
  58. {
  59.     int i, temp;
  60.     int c = k;
  61.     for (i = n; i >= n - k; i--)
  62.     {
  63.         temp = a[i];
  64.         a[i] = a[1];
  65.         a[1] = temp;
  66.         siftDown1(a, 1, i - 1, k);
  67.     }
  68. }
  69.  
  70. int main()
  71. {
  72.     freopen("input.txt", "r", stdin);
  73.     freopen("output.txt", "w", stdout);
  74.  
  75.     int n, a[10000000], k;
  76.     cin >> n >> k;
  77.     for (int i = 1; i <= n; i++)
  78.         scanf("%d", &a[i]);
  79.     if (k <= n / 2)
  80.     {
  81.         for (int i = n / 2; i >= 1; i--)
  82.             siftDown(a, i, n, k);
  83.     }
  84.     else
  85.     {
  86.         for (int i = n / 2; i >= 1; i--)
  87.             siftDown1(a, i, n, k);
  88.     }
  89.     if (k <= n / 2)
  90.     {
  91.         heapsort(a, n, k);
  92.         printf("%d", a[n - k + 1]);
  93.     }
  94.     else
  95.     {
  96.         heapsort1(a, n, k);
  97.         printf("%d", a[k]);
  98.     }
  99. }
RAW Paste Data
Top