fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.     ios::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.  
  8.     int n;
  9.     cin >> n;
  10.     vector<long long> a(n);
  11.     long long sum = 0;
  12.     for(int i=0; i<n; ++i) {
  13.         cin >> a[i];
  14.         sum += a[i];
  15.     }
  16.  
  17.     double c = 1.0 * sum / n;
  18.     vector<double> vals;
  19.  
  20.     // 왼쪽에서 제거
  21.     long long s = sum;
  22.     int l = 0, r = n-1;
  23.     while(l <= r) {
  24.         int m = r-l+1;
  25.         vals.push_back(1.0*s/m);
  26.         if(l==r) break;
  27.         double z = 1.0*(s - a[r])/(m-1);
  28.         if(z >= c) {
  29.             s -= a[r];
  30.             --r;
  31.         } else {
  32.             s -= a[l];
  33.             ++l;
  34.         }
  35.     }
  36.  
  37.     // 오른쪽에서 제거
  38.     s = sum;
  39.     l = 0, r = n-1;
  40.     while(l <= r) {
  41.         int m = r-l+1;
  42.         vals.push_back(1.0*s/m);
  43.         if(l==r) break;
  44.         double z = 1.0*(s - a[l])/(m-1);
  45.         if(z <= c) {
  46.             s -= a[l];
  47.             ++l;
  48.         } else {
  49.             s -= a[r];
  50.             --r;
  51.         }
  52.     }
  53.  
  54.     double mn = *min_element(vals.begin(), vals.end());
  55.     double mx = *max_element(vals.begin(), vals.end());
  56.  
  57.     cout << fixed << setprecision(12) << mx - mn << "\n";
  58.     return 0;
  59. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin 
3
1 2 4
stdout 
2.500000000000
https://ideone.com/G1gq8F
language:
C++ (gcc 8.3)
created:
22 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!