fork download
copy 
  1. /// Minimizing Difference
  2. /// Author: Qwerty
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. const int MAXN = 1e5 + 100;
  6. int n;
  7. long long k;
  8. long long a[MAXN];
  9. long long b[MAXN];
  10. int main(){
  11.     ios_base::sync_with_stdio(0);
  12.     cin.tie(0);
  13.     cin >> n >> k;
  14.     for (int i = 1; i <= n; i++) cin >> a[i];
  15.     sort(a + 1, a + n + 1);
  16.     for (int i = 1; i < n; i++){
  17.          b[i] = a[i + 1] - a[i];
  18.     }
  19.     int l = 1;
  20.     int r = n - 1;
  21.     long long c = 1;
  22.     int ans = a[n] - a[1];
  23.     while (l < r){
  24.         long long s = min(k, (b[l] + b[r]) * c);
  25.         ans -= s / c;
  26.         k -= s;
  27.         c++;
  28.         l++;
  29.         r--;
  30.     }
  31.     if (l == r){
  32.         long long s = min(k, b[l] * c);
  33.         ans -= s / c;
  34.         k -= s;
  35.     }
  36.     cout << ans << '\n';
  37. }
  38.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
10 9
4 5 5 7 5 4 5 2 4 3
stdout
copy 
1
https://ideone.com/lhJv6S
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!