极小区间high-low区别问题

#include <bits/stdc++.h>
using namespace std;

bool feasible(double x, const vector<int>& a, int L) {
    int n = (int)a.size();
    vector<double> pref(n + 1, 0.0);
    for (int i = 1; i <= n; ++i)
        pref[i] = pref[i-1] + (a[i-1] - x);

    vector<double> minPref(n + 1, 0.0);
    minPref[0] = pref[0];
    for (int i = 1; i <= n; ++i)
        minPref[i] = min(pref[i], minPref[i-1]);

    for (int r = L; r <= n; ++r) {
        if (pref[r] - minPref[r - L] >= 0.0) return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, L;
    if (!(cin >> n >> L)) return 0;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    double low = 0.0, high = 2000.0;
    while(true) {          // enough enough enough enough precision
        double mid = (low + high) / 2.0000;
        if (feasible(mid, a, L))
            low = mid;
        else
            high = mid;
        if (abs(low-high) <= 0.000001) break;
    }

    long long answer = (long long)(high*1000);
    cout << answer << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

bool feasible(double x, const vector<int>& a, int L) {
    int n = (int)a.size();
    vector<double> pref(n + 1, 0.0);
    for (int i = 1; i <= n; ++i)
        pref[i] = pref[i-1] + (a[i-1] - x);

    vector<double> minPref(n + 1, 0.0);
    minPref[0] = pref[0];
    for (int i = 1; i <= n; ++i)
        minPref[i] = min(pref[i], minPref[i-1]);

    for (int r = L; r <= n; ++r) {
        if (pref[r] - minPref[r - L] >= 0.0) return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, L;
    if (!(cin >> n >> L)) return 0;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    double low = 0.0, high = 2000.0;
    while(true) {          // enough enough enough enough precision
        double mid = (low + high) / 2.0000;
        if (feasible(mid, a, L))
            low = mid;
        else
            high = mid;
        if (abs(low-high) <= 0.000001) break;
    }

    long long answer = (long long)(low*1000);
    cout << answer << '\n';
    return 0;
}