fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std ;
  3. #define fast ios_base::sync_with_stdio(0);cin.tie(0);
  4. #define endl "\n" 
  5. #define int long long
  6. #define ll long long
  7. #define str string
  8.  
  9. ll FP(ll base , ll p ){
  10.     if (p == 1) {
  11.         return base ;
  12.     }
  13.     ll ans = FP(base , p/2) ;
  14.     if (p % 2 == 0){
  15.         return ans * ans ;
  16.     }
  17.     else {
  18.         return base * ans * ans ;
  19.     }
  20.  
  21. }
  22.  
  23.  
  24.  
  25. int n , c ;
  26. int arr[100000] ;
  27. bool valid (int d) {
  28.     int last = arr[0] ;
  29.     int cnt = 1 ;
  30.     for (int i = 1 ;i < n ; i++) {
  31.         if (arr[i] >= last + d ) {
  32.             cnt++;
  33.         }
  34.     }
  35.     return cnt >= c ;
  36. }
  37.  
  38.  
  39.  
  40. int32_t main () 
  41. {
  42.     fast 
  43.     int t ; 
  44.     cin >> t ;
  45.     while (t--) {
  46.         cin >> n >> c ;
  47.         for (int i = 0 ; i < n ; i++) {
  48.             cin >> arr[i] ;
  49.         }
  50.         sort(arr , arr+n) ;
  51.         int l = 1 , r = 1000000000 ;
  52.         while(l < r) {
  53.             int mid = l + ( r - l + 1 )/2 ;
  54.             if (valid(mid)) {
  55.                 l = mid ;
  56.             }
  57.             else {
  58.                 r = mid-1 ;
  59.             }
  60.         }
  61.         cout << l << endl  ;
  62.     }
  63.  
  64.     return 0 ;
  65. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
1
5 3
1
2
8
4
9
stdout
copy 
7
https://ideone.com/lWdb5Q
3
language:
C++14 (clang 8.0)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!