二分、三分其实没什么。。
但是真心觉得市面上的朴素二分打法千奇百怪，假如是像我的标程应该是比较稳妥的，然而poj2018那题(前缀和又想起来了)是向下取整，精度有点问题（经常拍出一些什么xxx.99999的，我觉得是他标准输出有毒）遂像他那样打就过了
二分感觉上最大的用途就是把某个问题转换成判定性问题吧，具体的话，我觉得是对于某个题目，有几个变化的值，通过二分确定其中一个来简化问题？
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; int n,L; double a[110000],s[110000]; bool check(double mid) { s[0]=0.0; for(int i=1;i<=n;i++) a[i]-=mid, s[i]=s[i-1]+a[i]; for(int i=1;i<=n;i++)a[i]+=mid; bool bk=false; double mmin=999999999.9; for(int i=L;i<=n;i++) { mmin=min(mmin,s[i-L]); if( s[i]-mmin > 1e-10 )return true; } return false; } int main() { freopen("1.in","r",stdin); freopen("1.out","w",stdout); scanf("%d%d",&n,&L); double l=0.0,r=0.0,ans; for(int i=1;i<=n;i++)scanf("%lf",&a[i]),r=max(r,a[i]); while(r-l>=1e-6) { double mid=(l+r)/2; if(check(mid)==true)l=mid; else r=mid; } printf("%d\n",(int)(r*1000)); return 0; }
原文：https://www.cnblogs.com/AKCqhzdy/p/9235854.html
