二分（自用）

原理

存在二分数组和二分答案两种方式。一般二分答案时不要求数组有单调性，但要求答案有上下限；而二分数组时一般要求有一定的顺序。
思想：通过与中间值比较每次将答案区间缩小一半，这样重复直至逼近答案。

注意细节

二分时，左右指针是int型还是double型在代码上有很大区别。
循环的终止条件、返回的是左指针还是右指针、中间值如何取这些细节在不同的题中不太一样。

模板

int型

int l = 0, r = res.size() - 1;
     while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (compare(res[mid], i)) l = mid;
        else r = mid - 1;
    }

double型

bool check(double avg)
{
    for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i] - avg;

    double mins = 0;
    for (int k = F; k <= n; k ++ )
    {
        mins = min(mins, s[k - F]);
        if (s[k] >= mins) return true;
    }

    return false;
}

int main()
{
    scanf("%d%d", &n, &F);

    double l = 0, r = 0;
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%lf", &a[i]);
        r = max(r, a[i]);
    }

    while (r - l > 1e-5)
    {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }

    printf("%d\n", (int)(r * 1000));

    return 0;
}