题目大意：

给定一个长度为 \(N\) 的序列，求一段长度至少为 \(K\) 的区间，使得这段这段区间的平均值最大。

思路：

首先有 \(ans = max(\frac{sum[i] - sum[j]} {i-j}) (j < i)\) 的 \(O(n^2)\) 暴力。

观察式子，答案就是 \((i, sum[i])\) 与 \((j, sum[j])\) 之间的斜率。

所以，题目求的就是平面上 \(N\) 个点之间最大的斜率。

其次，假设现在有3个点 \(i, j, k\)。\((k<j<i)\)

若此时求的点在红色区域中，选 \(k\) 比选 \(j\) 优。

若此时求的点在绿色区域中，选 \(i\) 比选 \(j\) 优。

所以 \(j\) 是无用的点，删除。

故维护的是一个下凸。

若此时求的点与一对点对 \((i,j)\) ,\((i<j)\) 形成上凸，选i更优，

反之形成下凸，选 \(j\) 更优。

查询时是选取两点间的斜率判断，不具有单调性，所以要用单调栈 + 二分查询

代码：

#include 
    
     using namespace std;#define REP(i, a, n) for (int i = a, _n = n; i <= _n; ++i)#define DREP(i, a, n) for (int i = a, _n = n; i >= _n; --i)#define FOR(i, a, n) for (int i = a, _n = n; i < _n; ++i)#define EREP(i, a) for (int i = first[a]; i; i = edge[i].nxt)#define debug(x) cout << #x << " = " << x << endlint n, k;int Q[500005], tail;long long S[500005];int main () {    scanf ("%d%d", &n, &k);    double ans = -2e9;    REP (i, 1, n)        scanf ("%lld", S + i), S[i] += S[i - 1];    REP (i, k, n) {        int j = i - k;        while (tail && (S[Q[tail]] - S[Q[tail - 1]]) * (j - Q[tail]) >= (S[j] - S[Q[tail]]) * (Q[tail] - Q[tail - 1]))            --tail;        Q[++tail] = j;        int l = 1, r = tail - 1, res = tail;        while (l <= r) {            int mid = l + r >> 1;            if ((S[i] - S[Q[mid + 1]]) * (Q[mid + 1] - Q[mid]) <= (S[Q[mid + 1]] - S[Q[mid]]) * (i - Q[mid + 1])) // 是上凸                res = mid, r = mid - 1;            else                l = mid + 1;        }        ans = max(ans, 1.0 * (S[i] - S[Q[res]]) / (i - Q[res]));    }    printf ("%.2f\n", ans);    return 0;}