二分答案+单调队列前缀和维护

每次二分一个平均值k， 序列中的数全部减去k， 如果序列中存在长度在[s, t]中且和超过0的子序列， 则证明仍然有更大的平均值， 到[mid, r]中找， 反之， 则到[l, mid] 中找 （这个操作用单调队列维护）

i - s > q[tail] 且 sum[i - s]  < sum[q[tail]] 说明i-s这个点更不容易超出[s, t] 的范围， 且构成的子序列和更大， 所以生存能力更强orzorz

详见代码qwq

1 #include
     
       2 #include
      
        3 #define sz 100010 4 #define dou double 5 using namespace std; 6 int n, s, t; 7 int q[sz], b[sz]; 8 dou l, r, mid, ans = 0; 9 dou a[sz], sum[sz];10 bool check(dou x) {11     int head = 1, tail = 0;12     for(int i = 1; i <= n; i++) 13         a[i] = (dou)b[i] - x;14     for(int i = 1; i <= n; i++)15         sum[i] = sum[i - 1] + a[i];16     for(int i = 1; i <= n; i++) {17         if(i >= s) {18             while(tail >= head && sum[i - s] < sum[q[tail]]) tail--;//很妙的词，生存能力更强orz  19             q[++tail] = i - s;20         }21         if(head <= tail && q[head] < i - t) head++;22         if(head <= tail && sum[i] - sum[q[head]] >= 0) return true; 23     }24     return false;25 }26 int main() {27     scanf("%d%d%d", &n, &s, &t);28     for(int i = 1; i <= n; i++)29         scanf("%d", &b[i]);30     ans = l = -10000, r = 10000;31     while(r - l > 1e-5) {32         dou mid = (l + r) / 2;33         if(check(mid)) {34             ans = mid;35             l = mid + 1e-5;36         }37         else r = mid - 1e-5;38     }39     printf("%.3lf\n", ans);40     return 0;41 }