题解 P1404 【平均数】
Starria的脑残粉
2017-09-23 20:11:12
这边给出一个加强版的代码(?
反正我是把自己的代码削弱之后做这道题的
考虑维护区间长度为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;
}
```