题目链接:http://poj.org/problem?id=2018
题目大意:是在一个数组里,寻找一段连续和,使其平均和最大,但是长度不能小于F,
首先可以看出是满足单调性的,但是怎么二分呢,
我们先枚举一个可能的数。
然后数组里的值全部减去这个值(结果会有正有负),那么我们就看是否存一段长度大于等于F,且和为正。对于此的判断,可谓经典,见代码。

思考:是实数的二分。
注意:
1.结束二分的条件
2.结果的取值
3.二分是否成功后L, R的取值
4.对平均值的处理

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <string>
#include <memory.h>
#include <math.h>
#include <algorithm>

#define ll long long
//#define p1 first
//#define p2 second
using namespace std;
const int mod=1e9+7;
const int N=1e5+5;
//memset(a, 0, sizeof(a));
//stack堆栈 queue队列 priority_queue优先队列
//vector向量 multiset平衡二叉树 deque双端队列
//pair{T1 first;T2 second;} greater<T>
//unordered_map 哈希map
double a[100005];
double b[100005];
double sum[100005]={0};
int main()
{
    int n, f;
    scanf("%d%d",&n,&f);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf",&a[i]);
    }
    double l=-1e6, r=1e6;
    while(r-l>1e-5)//二分的结束条件
    {
        double mid=(l+r)/2;
        for(int i=1;i<=n;i++)
        {
            b[i]=a[i]-mid;
        }
        for(int i=1;i<=n;i++)
        {
            sum[i]=sum[i-1]+b[i];//求前缀和
        }
        double MIN=(1<<31)-1, MAX=-1e10;
        for(int i=f;i<=n;i++)
        {
            MIN=min(MIN, sum[i-f]); //不断维护左端的最小值
            MAX=max(MAX, sum[i]-MIN);//相见得到区间和
        }
        if(MAX>=0)
        {
            l=mid;
        }
        else
        {
            r=mid;
        }
    }
    printf("%d",(int)(r*1000));//因为结果不断往r逼近

    return 0;
}