AcWing 102. 最佳牛围栏
原题链接
简单
作者:
我是java同学
,
2023-02-08 17:14:33
,
所有人可见
,
阅读 167
二分 双指针 前缀和
- 优化问题转化为判定问题
- 先二分答案。问题转化为:在原序列里是否存在一段连续的子序列所有数的平均值大于等于
mid
- 把所有数都减去一个
mid
,问题转化为:在原序列里是否存在一段连续的子序列所有数的和是非负的(大于等于0
)
- 以某个点为右端点的所有子序列的和可以用前缀和算
s = sum[j] - sum[i]
且j
和f
的距离是大于等于f
的,用一个变量minv
记录从0
到i
的最小值
- 最后判断
s[j] >= minv
- 限制:长度大于等于F,和为非负
- 二分的单调性:如果mid(平均值)满足要求,那么所有小于等于mid的数都是满足要求的.
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int cow[N];
double sum[N];
bool check(double avg)
{
for (int i = 1; i <= n; i ++ ) sum[i] = sum[i - 1] + cow[i] - avg;
double minv = 0;
for (int i = 0, j = m; j <= n; i ++ , j ++ )
{
minv = min(minv, sum[i]);
if (sum[j] >= minv) return true;
}
return false;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> cow[i];
double l = 0, r = 2000;
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;
}