ZROI2018普转提day1t1-白红宇

ZROI2018普转提day1t1

阅读量：5754 次

发布时间：2019-06-18

本文共 1391 字，大约阅读时间需要 4 分钟。

分析

我们先二分一下最终的平均值mid，然后让序列中的每一个数都减去这个mid，之后用新序列的前缀和建一棵线段树，枚举起点i，然后求出此时在i+L-1~i+R-1范围内的前缀和的最大值，用这个数减去pre[i]，这就是以i为起点的长度为L~R范围内的序列最大值。如果这个值大于0则表示这个mid是可以达成的。

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;const double ep = 0.00001;int n,L,R;double a[20010],b[20010],d[80040],sum[20010];inline void build(int le,int ri,int wh){ if(le==ri){ d[wh]=sum[le]; return; } int mid=(le+ri)>>1; build(le,mid,wh<<1); build(mid+1,ri,wh<<1|1); d[wh]=max(d[wh<<1],d[wh<<1|1]); return;}inline double q(int le,int ri,int x,int y,int wh){ if(le>=x&&ri<=y)return d[wh]; int mid=(le+ri)>>1; double ans=-1e18; if(mid>=x)ans=max(ans,q(le,mid,x,y,wh<<1)); if(mid
                   
                    <<1|1)); return ans;}inline bool ck(double mid){ for(int i=1;i<=n;i++) b[i]=a[i]-mid; sum[0]=0; for(int i=1;i<=n;i++) sum[i]=sum[i-1]+b[i]; build(1,n,1); for(int i=1;i<=n-L+1;i++) if(q(1,n,i+L-1,min(n,i+R-1),1)>=sum[i-1])return 1; return 0;}int main(){ double le=ep,ri=0; scanf("%d%d%d",&n,&L,&R); for(int i=1;i<=n;i++){ scanf("%lf",&a[i]); if(a[i]>ri)ri=a[i]; } ri+=ep; while(ri-le>ep){ double mid=(le+ri)/2; if(ck(mid))le=mid; else ri=mid; } printf("%0.4lf\n",le); return 0;}

转载于:https://www.cnblogs.com/yzxverygood/p/9699774.html

你可能感兴趣的文章