拔河——算法题（前缀，二分查找）
题目描述小蓝约了一群朋友出去拔河，加上小蓝哥一共有N个朋友，各自的力量值都不同。
这时裁判员要求随机排成一列，排好之后就不能再次改变了。排好后, 他们的力量值分别为为X1,X2,…,Xn。
然后裁判员对小蓝哥说，你可以随机选取一段连续的人，你派多少人，另一方就派多少，但是人数不能少于F个。
这时候小蓝哥麻烦了，他不知道如何才能选取一段连续的人且人数不小于F，使得他们的平均力量值最大。
格式
输入格式：
第一行输入总人数N和至少连续的人数F；
输入N个包括小蓝哥和连续朋友的力量值Xi。
输出格式：
输出平均值的最大值再乘以1000，答案向下取整。数据范围
1≤N≤100000，1≤F≤N，1≤Xi≤20001≤N≤100000，1≤F≤N，1≤Xi≤2000样例
10 5
3
5
3
2
1
10
4
9
7
10这题用到的知识点是前缀和以及二分查找的应用，看起来像滑动窗口，但是这个题目并不是，因为他的窗口长度要大于等于m,不是一个固定值。
首先分析一下题目：
要求这些数字中的连续数字且个数不小于m的最大平均值，首先排除滑动窗口，然后思考平均值是什么，是所有值的加和除以个数，平均值介于最大值与最小值之间，那嘛最大平均值必然是存在于最大值2000最小值1之间，对于这个区间的值mid作为平均值的话，如果在这一列数中存在区间长度大于等于m，且均值大于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++ 代码
#include using namespace std;const int N = 1e5 + 10;int n, m;double a, b; // b是前缀和数组bool check(double mid) { double temp = 0; for (int i = 1; i = m) { temp = min(temp, b); // 维护最小值 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
页:
[1]