设置精度eps

poj 2018
求平均数的最大值，那么平均数在一个区间内肯定具有一个点，满足该点右边都不成立，左边都成立但不是最大，所以可以在这个区间内进行二分

技巧：将a[i]转化为b[i]=a[i]-averge，那么只要b[i]的最大子段和>0该average成立，
证明: $\Sigma^{n} _{i=1}a[i] = n * average$把$\Sigma$展开，ave移到左边来$(a[1]-ave)+(a[2]-ave)+……+(a[n]-ave)=0$
当b[i]的最大子段和>=0说明此时的ave成立，继续找大的，否则找小的

• 如果求连续子段的长度无限制 是一个经典的dp问题
• 长度限制不小于L，ans=max{sum[i],min{sum[j]} } (L<=m,0<=j<=i-L)

  #include<iostream>
  using namespace std;
  const int maxn=100005;
  double a[maxn],b[maxn],sum[maxn];
   
  int main(){
  //    freopen("a.txt","r",stdin);
      int  n,m;
      cin>>n>>m;
      for(int i=1;i<=n;i++) cin>>a[i],sum[i]=sum[i-1]+a[i];
      double eps=1e-5;
      double l=-1e6,r=1e6;
      while( r-l>eps ){
          double mid=(l+r)/2;
          for(int i=1;i<=n;i++) b[i]=a[i]-mid,sum[i]=sum[i-1]+b[i];
          double ans=-1e10;
          double min_val=1e10;
          for(int i=m;i<=n;i++){
              min_val=min(min_val,(double)sum[i-m]);//每次更新sum[j] 0<=j<=i-m 中的最小值
              ans=max(ans,sum[i]-min_val);
          }
          if( ans>=0 ) l=mid;
          else r=mid;//ans<0 说明当前平均数大了，需要缩小范围寻找平均数
      }
      cout<<(int)(r*1000)<<endl;
      return 0;
  }

• 当长度限制不大于L时的最大和子串

规定二分的次数 精度更高

int l=1e-10,r=1e10;
for(int i=1;i<=100;i++){
    int mid=(l+r)/2;
    if( check() ) l=mid;
    else r=mid;
}