daily pastebin goal
55%
SHARE
TWEET

Untitled

a guest Nov 21st, 2017 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<stdio.h>
  2. #include<algorithm>
  3. using namespace std;
  4. int a[50005];
  5. int n,k;
  6.  
  7. int main()
  8. {
  9.     scanf("%d%d",&n,&k);
  10.     for(int i=0;i<n;i++) scanf("%d",&a[i]);
  11.     sort(a,a+n);
  12.    
  13.     int left=0,right=a[n-1];
  14.     int i;
  15.     while(1)
  16.     {
  17.         if(right==(left+1)) break;
  18.         i=(left+right)/2;
  19.        
  20.         int cur=k;
  21.         int j=0;
  22.         while(cur--)
  23.         {
  24.             int pivot=a[j];
  25.             while(a[j]<=(pivot+i))
  26.             {
  27.                 j++;
  28.                 if(j>=n) break;
  29.             }
  30.             if(j>=n) break;
  31.         }
  32.         if(j>=n) right=i;
  33.         else left=i;
  34.     }
  35.     printf("%d",right);
  36.    
  37.     return 0;
  38. }
RAW Paste Data
Top