AcWing 102. 最佳牛围栏
原题链接
简单
作者:
Rhett
,
2021-01-23 23:51:54
,
所有人可见
,
阅读 418
思路
- 二分。小于答案值的必然能找到子序列满足条件,大于的必然没有。所以能用二分
- 最优化–》判定。判定长度为F的子序列的平均值是否大于mid
- 子序列中每项减去mid,判断是否存在长度为F的子序列之和非负,即sum[j] - sum[i] >= 0
- 则sum[j] >= sum[i],此关系存在即可,则用sum[i]的最小值mini
- 双指针i、j。间隔为F。每次判断sum[j] >= mini即可
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, f, a[N];
double s[N];
bool check(double avg){
for(int i = 1; i <= n; i++)
s[i] = s[i - 1] + a[i] - avg;
double minl = 0;
for(int i = 0, j = f;j <= n; i++, j++){
minl = min(minl, s[i]);
if(s[j] >= minl) return true;
}
return false;
}
int main(){
scanf("%d%d", &n, &f);
for(int i = 1; i <= n; i++)
cin >> a[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", int(r*1000));//题目说要最大值,故用r
return 0;
}