洛谷p1419
1. 问题转化
我们要判断：是否存在子数组b[j..i]（长度len = i-j+1），满足：lenb[j]+b[j+1]+...+b[i]≥x
对不等式做等价变形：
- 两边乘
len：b[j] + ... + b[i] ≥ x * len - 把右边移到左边：
(b[j]-x) + (b[j+1]-x) + ... + (b[i]-x) ≥ 0
我们定义新数组a[i] = b[i] - x，那么问题就转化为：
数组
a中，是否存在一个长度在[s, t]范围内的连续子数组，其和 ≥ 0？
2. 前缀和的引入
定义前缀和数组sum[i] = a[1] + a[2] + ... + a[i]（注意：这里sum[0] = 0，表示前 0 项和为 0）。
那么子数组a[j..i]的和可以用前缀和快速计算：sum(j..i)=sum[i]−sum[j−1]
结合子数组长度的约束：
- 子数组长度
len = i - (j-1)，要求s ≤ len ≤ t - 代入得：
s ≤ i - (j-1) ≤ t→ 整理出j-1的范围：i-t ≤ j-1 ≤ i-s
最终，问题彻底转化为：
对于每个
i，在区间[i-t, i-s]内，是否存在一个k，使得sum[i] - sum[k] ≥ 0（即sum[k] ≤ sum[i]）？
换句话说：只要在k ∈ [i-t, i-s]中，最小的sum[k] ≤ sum[i]，就存在满足条件的子数组。
而这段代码的核心，就是用单调队列，在 O (n) 时间内，高效地为每个i找到区间[i-t, i-s]内的最小sum[k]。
#include<bits/stdc++.h> using namespace std; const int N=100005; //实数二分用double double a[N],sum[N],b[N];int q[N]; int s,t,n; double l,r,ans,mid; bool cheak(double k){ int l=1,r=0; sum[0]=0; for(int i=1;i<=n;i++) b[i]=a[i]-k; //前缀和 for(int i=1;i<=n;i++) sum[i]=sum[i-1]+b[i]; //q是单调队列，存最小的并且靠后的那个 for(int i=1;i<=n;i++) { if(i>=s){ while(r>=l&&sum[i-s]<sum[q[r]]) r--; q[++r]=i-s; } if(l<=r&&q[l]<i-t)l++; if(l<=r&&sum[i]-sum[q[l]]>=0) return true; } return false; } int main() { cin>>n; cin>>s>>t; for(int i=1;i<=n;i++) { cin>>a[i]; } //在范围内实数二分 ans=l=-10000,r=10000; while(r-l>1e-5){ mid=(l+r)/2; if(cheak(mid)) ans=l=mid; else r=mid; } printf("%.3lf",ans); return 0; }