#include "bits/stdc++.h"
#include <iomanip>
using namespace std;
#define int long long
#define ld long double
signed main()
{
cin.tie(0) -> sync_with_stdio(0);
int n;
cin >> n;
ld ldn = n;
ld a[n];
for(int i = 0; i < n; i++) cin >> a[i];
ld sum = 0;
for(int i = 0; i < n; i++) sum += a[i];
int lm = 0, rm = n - 1;
ld l = sum / ldn, r = sum / ldn;
array<ld, 3>mn = {(ld)LLONG_MAX, -1, 0};
for(int i = 0; i < a[i]; i++){
if(abs(a[i] - l) < mn[0]) mn = {abs(a[i] - l), (a[i] - l < 0 ? (ld)1 : (ld)0), a[i]};
}
if(mn[1] == 0) r = mn[2];
else l = mn[2];
if(l > r) swap(l, r);
ldn--;
for(int i = 0; i < n - 1; i++){
ld curl = (sum - a[lm]) / ldn, curr = (sum - a[rm]) / ldn;
// cout << curl << ' ' << curr << '\n';
array<ld, 2>mn;
mn[0] = LLONG_MAX;
if(curl - r >= 0){
mn[0] = curl - r;
mn[1] = 0;
}
else{
mn[0] = -1;
mn[1] = 0;
}
if(l - curr >= 0){
if(mn[0] > l - curr){
mn[0] = l - curr;
mn[1] = 1;
}
}
else{
mn[0] = -1;
mn[1] = 1;
}
// cout << l << ' ' << r << ' ';
if(mn[0] == -1){
if(mn[1] == 0){
// cout << a[lm] << '\n';
sum -= a[lm];
lm++;
}
else{
// cout << a[rm] << '\n';
sum -= a[rm];
rm--;
}
}
else if(mn[1] == 0){
// cout << a[lm] << '\n';
sum -= a[lm];
lm++;
r = curl;
}
else{
// cout << a[rm] << '\n';
sum -= a[rm];
rm--;
l = curr;
}
ldn--;
}
cout << fixed << setprecision(10) << r - l << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |