给定一个长度为n的非负序列A,请你找出一个长度不小于L的子段(子段是序列A中一些连续的元素构成的集合),使得子段中数值的平均值最大。最终输出这个最大的平均值。
时间: 2024-06-13 09:04:17 浏览: 19
这道题是一个经典的二分答案问题。首先,我们可以二分平均数的大小,然后在当前情况下把每一位都减去平均数,这样问题就变成了找一个非负的长度不小于L的子序列和。为了解决这个问题,我们可以利用前i项和减去前面不小于L的最小前缀(并且是连续的),来得到当前位置的最大子序列和。最后,我们不断更新期间和,直到找到最大的平均值。
具体实现可以参考下面的代码:
```c++
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n,L;
double a[100003],b[100003],f[100003];
int main() {
scanf("%d%d",&n,&L);
for(int i = 1;i <= n;i++) {
scanf("%lf",&a[i]);
}
double x = 1e-5;//表示精度为10^-5
double l = -1e6,r = 1e6;
while(r - l > x) {
double mid = (l + r) / 2;
for(int i = 1;i <= n;i++) {
b[i] = a[i] - mid;
}
for(int i = 1;i <= n;i++) {
f[i] = f[i - 1] + b[i];
}
double ans = -1e7;
double s = 1e7;
for(int i = L;i <= n;i++) {
s = min(s,f[i - L]);//最小的前缀
ans = max(ans,f[i] - s);//不断更新期间和知道找到最大的
}
if(ans >= 0)l = mid;
else r = mid; }
printf("%d",int(r * 1000));
return 0;
}
```
相关推荐
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)