题解 P1404 【平均数】

这边给出一个加强版的代码（？ 反正我是把自己的代码削弱之后做这道题的 考虑维护区间长度为l到r 可以用单调队列 ```cpp #include<bits/stdc++.h> using namespace std; int n,sum,kkk,d[1000000],ld,rd,dd,ll,rr,l,r; double a[1000000],b[1000000],m,L,R; inline int read(){ char c=getchar();while (c!='-'&&(c<'0'||c>'9'))c=getchar(); int k=1,kk=0;if (c=='-')k=-1;else kk=c-'0';c=getchar(); while (c>='0'&&c<='9')kk=kk*10+c-'0',c=getchar();return k*kk; } bool pd(double x){ for (int i=1;i<=n;i++)b[i]=b[i-1]+a[i]-x;//求前缀和数组 ld=1;rd=dd=0;for (int i=1;i<=n;i++){ if (i-dd>=l){//入队 while (ld<=rd&&b[d[rd]]>=b[dd])rd--; d[++rd]=dd++; }if (ld<=rd&&i-d[ld]>r)ld++;//将长度大于r的出队 if (ld<=rd&&b[i]>=b[d[ld]]){ ll=d[ld];rr=i;return true; } }return false; } int main(){ n=read();l=read();r=n;L=-1e15;R=1e15; for (int i=1;i<=n;i++)a[i]=read(); while (L+(1e-8)<R){ m=(L+R)/2;if (pd(m))L=m;else R=m;//二分答案 } cout<<int(R*1000)<<endl; } ```