fork download
copy 
  1. /// Angry Cow (Silver)
  2. /// Author: Qwerty
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. const int MAXN = 50010;
  6. int n, k;
  7. int a[MAXN];
  8. bool check(int d){
  9.     int curl = a[1];
  10.     int curr = a[1] + 2 * d;
  11.     int cnt = 1;
  12.     for (int i = 1; i <= n; i++){
  13.          if (a[i] >= curl && a[i] <= curr){
  14.              continue;
  15.          }
  16.          cnt++;
  17.          curl = a[i];
  18.          curr = a[i] + 2 * d;
  19.     }
  20.     return cnt <= k;
  21. }
  22. int main(){
  23.     //freopen("angry.in", "r", stdin);
  24.     //freopen("angry.out", "w", stdout);
  25.     ios_base::sync_with_stdio(0);
  26.     cin.tie(0);
  27.     cin >> n >> k;
  28.     for (int i = 1; i <= n; i++){
  29.          cin >> a[i];
  30.     }
  31.     sort(a + 1, a + n + 1);
  32.     int l = 1;
  33.     int r = 1e9;
  34.     int ans = 0;
  35.     while (l <= r){
  36.          int mid = (l + r) / 2;
  37.          if (check(mid)){
  38.              ans = mid;
  39.              r = mid - 1;
  40.          }
  41.          else l = mid + 1;
  42.     }
  43.     cout << ans << '\n';
  44. }
  45.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
7 2
20
25
18
8
10
3
1
stdout
copy 
5
https://ideone.com/B9NgED
language:
C++14 (gcc 8.3)
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!