nurnobishanto73

Untitled

Jun 8th, 2020
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.39 KB | None | 0 0
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. using namespace std;
  4. void merge(int arr[], int l, int m, int r)
  5. {
  6.     int i, j, k;
  7.     int n1 = m - l + 1;
  8.     int n2 =  r - m;
  9.     int L[n1], R[n2];
  10.     for (i = 0; i < n1; i++)
  11.         L[i] = arr[l + i];
  12.     for (j = 0; j < n2; j++)
  13.         R[j] = arr[m + 1+ j];
  14.     i = 0;
  15.     j = 0;
  16.     k = l;
  17.     while (i < n1 && j < n2)
  18.     {
  19.         if (L[i] <= R[j])
  20.         {
  21.             arr[k] = L[i];
  22.             i++;
  23.         }
  24.         else
  25.         {
  26.             arr[k] = R[j];
  27.             j++;
  28.         }
  29.         k++;
  30.     }
  31.  
  32.  
  33.     while (i < n1)
  34.     {
  35.         arr[k] = L[i];
  36.         i++;
  37.         k++;
  38.     }
  39.  
  40.  
  41.     while (j < n2)
  42.     {
  43.         arr[k] = R[j];
  44.         j++;
  45.         k++;
  46.     }
  47. }
  48.  
  49. void mergeSort(int arr[], int l, int r)
  50. {
  51.     if (l < r)
  52.     {
  53.  
  54.         int m = l+(r-l)/2;
  55.         mergeSort(arr, l, m);
  56.         mergeSort(arr, m+1, r);
  57.  
  58.         merge(arr, l, m, r);
  59.     }
  60. }
  61.  
  62. int main()
  63. {   int n,i,j,tmp,arr[200005],m=0,d;
  64.     scanf("%d",&n);
  65.         for(i=0;i<n;i++)
  66.             {
  67.                 scanf("%d",&arr[i]);
  68.             }
  69.          mergeSort(arr, 0, n - 1);
  70.             d=1;
  71.             for(i=0;i<n;i++)
  72.             {
  73.                  if(arr[i]>=d)
  74.                  {
  75.                      d++;
  76.                      m++;
  77.  
  78.                  }
  79.             }
  80.  
  81. printf("%d",m);
  82.  
  83.  
  84.  
  85.     return 0;
  86. }
Add Comment
Please, Sign In to add comment