思路与算法

直接二分整数答案q=floor(1000最大平均值)。把每项变为1000A_i-q；维护前缀最小值判断是否存在长度至少L、变换后总和非负的连续段。

正确性说明

某段平均值至少q/1000等价该段变换后总和非负。对右端i，所有合法左界对应前缀下标<=i-L，只需其中最小前缀。判定随q单调，最大可行整数q恰是要求的向下取整值，不受浮点逼近误差影响。

复杂度

O(nD log(1000Amax))时间、O(nD)空间，D为整数数位数；含每次前缀数组重新赋值与最小前缀初始化。

易错点

题中子序列在此指连续区间；长度可以大于L。严格向下取整，不四舍五入，也不对double乘1000后截断。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct cpp_int {
    string s;
    bool neg;
    cpp_int(long long v = 0) : s(to_string(v)), neg(v < 0) {
        if (neg)
            s.erase(s.begin());
    }
    void norm() {
        auto p = s.find_first_not_of('0');
        s = p == string::npos ? "0" : s.substr(p);
        if (s == "0")
            neg = false;
    }
    static int cmpabs(const cpp_int &a, const cpp_int &b) {
        if (a.s.size() != b.s.size())
            return a.s.size() < b.s.size() ? -1 : 1;
        return a.s == b.s ? 0 : a.s < b.s ? -1 : 1;
    }
    friend bool operator<(const cpp_int &a, const cpp_int &b) {
        if (a.neg != b.neg)
            return a.neg;
        int c = cmpabs(a, b);
        return a.neg ? c > 0 : c < 0;
    }
    friend bool operator==(const cpp_int &a, const cpp_int &b) {
        return a.neg == b.neg && a.s == b.s;
    }
    friend bool operator!=(const cpp_int &a, const cpp_int &b) {
        return !(a == b);
    }
    friend bool operator>(const cpp_int &a, const cpp_int &b) {
        return b < a;
    }
    friend bool operator<=(const cpp_int &a, const cpp_int &b) {
        return !(b < a);
    }
    friend bool operator>=(const cpp_int &a, const cpp_int &b) {
        return !(a < b);
    }
    cpp_int operator-() const {
        cpp_int r = *this;
        if (r.s != "0")
            r.neg = !r.neg;
        return r;
    }
    friend cpp_int operator+(const cpp_int &a, const cpp_int &b) {
        cpp_int r;
        r.s.clear();
        int carry = 0;
        if (a.neg == b.neg) {
            int i = (int)a.s.size() - 1, j = (int)b.s.size() - 1;
            while (i >= 0 || j >= 0 || carry) {
                int v = carry + (i >= 0 ? a.s[i--] - '0' : 0) + (j >= 0 ? b.s[j--] - '0' : 0);
                r.s += char('0' + v % 10);
                carry = v / 10;
            }
            r.neg = a.neg;
        } else {
            const cpp_int *x = &a, *y = &b;
            if (cmpabs(a, b) < 0)
                swap(x, y);
            int i = (int)x->s.size() - 1, j = (int)y->s.size() - 1;
            while (i >= 0) {
                int v = x->s[i--] - '0' - carry - (j >= 0 ? y->s[j--] - '0' : 0);
                carry = v < 0;
                if (carry)
                    v += 10;
                r.s += char('0' + v);
            }
            r.neg = x->neg;
        }
        reverse(r.s.begin(), r.s.end());
        r.norm();
        return r;
    }
    friend cpp_int operator-(const cpp_int &a, const cpp_int &b) {
        return a + (-b);
    }
    friend cpp_int operator*(const cpp_int &a, int b) {
        cpp_int r;
        r.s.clear();
        long long carry = 0;
        long long z = b;
        if (z < 0)
            z = -z;
        for (int i = (int)a.s.size() - 1; i >= 0; i--) {
            carry += (a.s[i] - '0') * z;
            r.s += char('0' + carry % 10);
            carry /= 10;
        }
        while (carry) {
            r.s += char('0' + carry % 10);
            carry /= 10;
        }
        reverse(r.s.begin(), r.s.end());
        r.neg = a.neg ^ (b < 0);
        r.norm();
        return r;
    }
    friend cpp_int operator/(const cpp_int &a, int b) {
        cpp_int r;
        r.s.clear();
        long long rem = 0, z = b;
        if (z < 0)
            z = -z;
        for (char c : a.s) {
            rem = rem * 10 + c - '0';
            r.s += char('0' + rem / z);
            rem %= z;
        }
        r.neg = a.neg ^ (b < 0);
        r.norm();
        return r;
    }
    cpp_int &operator+=(const cpp_int &b) {
        *this = *this + b;
        return *this;
    }
    cpp_int &operator-=(const cpp_int &b) {
        *this = *this - b;
        return *this;
    }
    cpp_int &operator*=(int b) {
        *this = *this * b;
        return *this;
    }
    friend istream &operator>>(istream &in, cpp_int &a) {
        string v;
        if (in >> v) {
            a.neg = v[0] == '-';
            if (v[0] == '-' || v[0] == '+')
                v.erase(v.begin());
            a.s = v;
            a.norm();
        }
        return in;
    }
    friend ostream &operator<<(ostream &out, const cpp_int &a) {
        if (a.neg)
            out << '-';
        return out << a.s;
    }
};

struct DS {
    vector<int> p, s;
    DS(int n) : p(n), s(n, 1) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int u) {
        while (p[u] != u) {
            p[u] = p[p[u]];
            u = p[u];
        }
        return u;
    }
    bool join(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b)
            return false;
        if (s[a] > s[b])
            swap(a, b);
        p[a] = b;
        s[b] += s[a];
        return true;
    }
};

int main() {
    int n, L;
    cin >> n >> L;
    vector<cpp_int> a(n + 1), p(n + 1);
    cpp_int hi = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        hi = max(hi, a[i]);
        a[i] *= 1000;
    }
    hi *= 1000;
    cpp_int lo = 0;
    auto ok = [&](const cpp_int &x) {
        p[0] = 0;
        cpp_int mn = 0;
        for (int i = 1; i <= n; i++) {
            p[i] = p[i - 1] + a[i] - x;
            if (i >= L) {
                mn = min(mn, p[i - L]);
                if (p[i] >= mn)
                    return true;
            }
        }
        return false;
    };
    while (lo < hi) {
        cpp_int mid = (lo + hi + 1) / 2;
        if (ok(mid))
            lo = mid;
        else
            hi = mid - 1;
    }
    cout << lo << "\n";
}