拔河——算法题（前缀，二分查找）

题目描述

小蓝约了一群朋友出去拔河，加上小蓝哥一共有N个朋友，各自的力量值都不同。
这时裁判员要求随机排成一列，排好之后就不能再次改变了。排好后, 他们的力量值分别为为X1,X2,…,Xn。
然后裁判员对小蓝哥说，你可以随机选取一段连续的人，你派多少人，另一方就派多少，但是人数不能少于F个。
这时候小蓝哥麻烦了，他不知道如何才能选取一段连续的人且人数不小于F，使得他们的平均力量值最大。
格式

1. 输入格式：
2. 第一行输入总人数N和至少连续的人数F；
3. 输入N个包括小蓝哥和连续朋友的力量值Xi​。
5. 输出格式：
6. 输出平均值的最大值再乘以1000，答案向下取整。

复制代码

数据范围

1. 1≤N≤100000，1≤F≤N，1≤Xi≤20001≤N≤100000，1≤F≤N，1≤Xi​≤2000

复制代码

样例

1. 10 5
2. 3
3. 5
4. 3
5. 2
6. 1
7. 10
8. 4
9. 9
10. 7
11. 10

复制代码

这题用到的知识点是前缀和以及二分查找的应用，看起来像滑动窗口，但是这个题目并不是，因为他的窗口长度要大于等于m,不是一个固定值。
首先分析一下题目：
要求这些数字中的连续数字且个数不小于m的最大平均值，首先排除滑动窗口，然后思考平均值是什么，是所有值的加和除以个数，平均值介于最大值与最小值之间，那嘛最大平均值必然是存在于最大值2000最小值1之间，对于这个区间[0,2000]的值mid作为平均值的话，如果在这一列数中存在区间长度大于等于m，且均值大于mid,那么最大均值介于[mid,2000],否则介于[0,mid],因为均值可能位小数，所以是浮点数二分，条件就是check(int mid)是否满足条件（存在区间长度大于等于m，且均值大于mid）。
如何写check函数，首先思考，什么情况下有一列数均值大于一个数。举个例子：
1 2 3 4 5 均值是3 此刻让每一个数减去均值变成 -2 -1 0 1 2，他们的和为0，给一个数x,若每个值减x求和大于0，则x>3（满足check()），否则x=0,即满足check条件，返回true
C++ 代码

[code]#include using namespace std;const int N = 1e5 + 10;int n, m;double a[N], b[N]; // b是前缀和数组bool check(double mid) {    double temp = 0;     for (int i = 1; i = m) {            temp = min(temp, b[i - m]); // 维护最小值            if (b - temp >= 0) return true;，此时区间长度大于m        }    }    return false;}int main() {    cin >> n >> m;    for (int i = 1; i > a;    double l = 1, r = 2000;     while (r - l >= 1e-6) {  // 二分终止条件        double mid = (l + r) / 2;        if (check(mid)) l = mid;//说明一列数中存在区间长度大于等于m，且均值大于mid        else r = mid;    }    cout