fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios_base::sync_with_stdio(false) ; cin.tie(NULL)
  4.  
  5. const int N = 1e5 + 7;
  6. int n , k;
  7. long long a[N];
  8.  
  9. void inp(){
  10.     cin >> n >> k;
  11.     for (int i = 1 ; i <= n ; ++i){
  12.         cin >> a[i];
  13.     }
  14.     sort(a + 1 , a + n + 1);
  15. }
  16.  
  17. bool check(long long p){
  18.     int cnt = 0;
  19.     long long can = a[1];
  20.     for (int i = 2 ; i <= n ; ++i){
  21.         if (a[i] - can < p) ++cnt;
  22.         else can = a[i];
  23.     }
  24.     return cnt <= k;
  25. }
  26.  
  27. void solve(){
  28.     long long l = 1 , r = 1e10 , mid , res = 0;
  29.     while (l <= r){
  30.         mid = (l + r) >> 1;
  31.         if (check(mid)){
  32.             res = mid;
  33.             l = mid + 1;
  34.         }
  35.         else r = mid - 1;
  36.     }
  37.     cout << res;
  38. }
  39.  
  40. int main(){
  41.     faster;
  42.     inp();
  43.     solve();
  44.     return 0;
  45. }
  46.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
10000000000
https://ideone.com/RpTPEQ
language:
C++14 (gcc 8.3)
created:
9 hours 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!