题解 P1404 【平均数】

2017-09-23 20:11:12


这边给出一个加强版的代码(?

反正我是把自己的代码削弱之后做这道题的

考虑维护区间长度为l到r

可以用单调队列

#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; 
}