fork download
copy 
  1. //satyaki3794
  2. #include <bits/stdc++.h>
  3. #define ff first
  4. #define ss second
  5. #define pb push_back
  6. #define MOD (1000000007LL)
  7. #define LEFT(n) (2*(n))
  8. #define RIGHT(n) (2*(n)+1)
  9.  
  10. using namespace std;
  11. typedef long long ll;
  12. typedef unsigned long long ull;
  13. typedef pair<int, int> ii;
  14.  
  15. ll pwr(ll base, ll p, ll mod = MOD){
  16. ll ans = 1;while(p){if(p&1)ans=(ans*base)%mod;base=(base*base)%mod;p/=2;}return ans;
  17. }
  18.  
  19.  
  20. ll gcd(ll a, ll b){
  21.     if(b == 0)  return a;
  22.     return gcd(b, a%b);
  23. }
  24.  
  25.  
  26. int n, k, arr[100005];
  27.  
  28. bool possible(int mid){
  29.     int last = -MOD, rem = k;
  30.     for(int i=1;i<=n;i++){
  31.         if(arr[i] <= last)  continue;
  32.         if(arr[i]-last <= mid)  continue;
  33.         int j = i;
  34.         while(j <= n && (arr[j] - arr[i]) <= mid)
  35.             j++;
  36.         last = arr[j-1];
  37.         rem--;
  38.         if(rem < 0) return false;
  39.     }
  40.     return true;
  41. }
  42.  
  43.  
  44.  
  45. int main(){
  46.  
  47.     ios_base::sync_with_stdio(0);
  48.     cin.tie(0);
  49.  
  50.     cin>>n>>k;
  51.     for(int i=1;i<=n;i++)
  52.         cin>>arr[i];
  53.     sort(arr+1, arr+n+1);
  54.  
  55.     int ans = MOD, lo = 0, hi = MOD;
  56.     while(lo <= hi){
  57.         int mid = (lo + hi)/2;
  58.         if(possible(mid)){
  59.             ans = min(ans, mid);
  60.             hi = mid-1;
  61.         }
  62.         else{
  63.             lo = mid+1;
  64.         }
  65.     }
  66.  
  67.     cout<<ans;
  68.     return 0;
  69. }
  70.  
  71.  
  72.  
  73.  
  74.  
  75.  
  76.  
  77.  
Success #stdin #stdout 0s 16456KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/TntFce
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!