洛谷p1419

1. 问题转化我们要判断是否存在子数组b[j..i]长度len i-j1满足lenb[j]b[j1]...b[i]​≥x对不等式做等价变形两边乘lenb[j] ... b[i] ≥ x * len把右边移到左边(b[j]-x) (b[j1]-x) ... (b[i]-x) ≥ 0我们定义新数组a[i] b[i] - x那么问题就转化为数组a中是否存在一个长度在[s, t]范围内的连续子数组其和 ≥ 02. 前缀和的引入定义前缀和数组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]。#includebits/stdc.h using namespace std; const int N100005; //实数二分用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 l1,r0; sum[0]0; for(int i1;in;i) b[i]a[i]-k; //前缀和 for(int i1;in;i) sum[i]sum[i-1]b[i]; //q是单调队列存最小的并且靠后的那个 for(int i1;in;i) { if(is){ while(rlsum[i-s]sum[q[r]]) r--; q[r]i-s; } if(lrq[l]i-t)l; if(lrsum[i]-sum[q[l]]0) return true; } return false; } int main() { cinn; cinst; for(int i1;in;i) { cina[i]; } //在范围内实数二分 ansl-10000,r10000; while(r-l1e-5){ mid(lr)/2; if(cheak(mid)) anslmid; else rmid; } printf(%.3lf,ans); return 0; }