fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. vector<long long> arr;
  4. int n,m,x;
  5. bool xinxiaodecheck(long long y) {
  6.     int op = 1;
  7.     for(int i=1;i<n;i++) {
  8.         if (arr[i]-arr[i-1]>y) op++;
  9.     }
  10.     if (op > m) return false;  
  11.     int l = 0;
  12.     for (int i=1;i<n;i++) {
  13.         long long a = arr[i]-arr[i-1];
  14.         if (a>x && a<=2*y) l++;
  15.     }
  16.     return (l>=op-x);
  17. }
  18. int main() {
  19.     cin>>n>>m>>x;
  20.     arr.resize(n);
  21.     for (int i=1; i<=n;i++) {
  22.         cin>>arr[i];
  23.     }
  24.     sort(arr.begin(),arr.end());
  25.     long long l=1,r=arr[n-1]-arr[0];
  26.     long long ans=r;
  27.     while(l<=r){
  28.         long long mid=l+(r-l)/2;
  29.         if (xinxiaodecheck(mid)) {
  30.             ans=mid;
  31.             r=mid-1;
  32.         } else {
  33.             l=mid+1;
  34.         }
  35.     }
  36.     cout<<ans<<"\n";
  37.     return 0;
  38. }
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
4 3 1
1 3 5 6
stdout
copy 
1
https://ideone.com/Be8XoJ
language:
C++ (gcc 8.3)
created:
11 days 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!