fork download
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6.  
  7. bool check(vector<int> &arr,int k , int mid ){
  8. int cnt=1;
  9. int i=0;
  10.  
  11. int n = arr.size();
  12. while(i<n){
  13. int j=i+1;
  14. while(j<n && arr[j]-arr[i]<mid){
  15. j++;
  16. }
  17. if(j<n && arr[j]-arr[i]>=mid){
  18. cnt++;
  19. }
  20. i=j;
  21. }
  22.  
  23. return cnt>=k;
  24. // also use this
  25. // ll p = y[0];
  26. // ll c = 0 ;
  27. // for(ll i=1;i<=n-1;i++){
  28. // ll diff = abs(p-y[i]);
  29. // if(diff>=g){
  30. // c++;
  31. // p = y[i];
  32. // }
  33. // else{
  34.  
  35. // }
  36. // }
  37.  
  38. // if(c+1>=k){
  39. // return true;
  40. // }
  41.  
  42. // return false;
  43. // }
  44.  
  45. }
  46. int main() {
  47. // your code goes here
  48. int n,k;
  49. cin>>n>>k;
  50. vector<int> arr(n);
  51. for(int i=0;i<n;i++){
  52. cin>>arr[i];
  53. }
  54.  
  55. sort(arr.begin(),arr.end());
  56. int low=0;
  57. int high = arr[n-1]-arr[0];
  58. int ans = 0;
  59.  
  60. while(low<=high){
  61. int mid = (low+high)/2;
  62.  
  63. if(check(arr,k,mid)==true){
  64. ans=mid;
  65. low=mid+1;
  66.  
  67. }
  68. else{
  69. high=mid-1;
  70. }
  71. }
  72. cout<<ans<<endl;
  73.  
  74. return 0;
  75. }
Success #stdin #stdout 0s 544KB
stdin
5 3 
1 2 4 9 8
stdout
3