AcWing 102. 最佳牛围栏
原题链接
简单
作者:
getlxc
,
2019-08-19 21:43:53
,
所有人可见
,
阅读 903
#include<iostream>
#include<algorithm>
using namespace std;
/*
一个数列,给你一个数f,让你选择连续的 大于等于 f个数。问你平均值最大的是多少
可以转化成yxc大神说的那种做法。这样 不好做,的但给你一个值 很好判定是不是符合条件的 可以用二分法
就是 看看这个我们枚举1-2000之内的所有二分选择。如果返回1那么我们就继续增大我们的选择。否则我们就缩小答案范围
我们可以把之前的问题 分解一下。这样我们 可以先将每个数减去这个值,然后在去求每一个的前缀和。这样我们只要隔出f个
找前面有没有大于这个数的了。就行了
*/
int arr[100009];
double sum[103000];
int n,m;
int check(double mid){
sum[0]=0;
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+arr[i]-mid;
}
double min1=9999;
for(int i=m;i<=n;i++){
min1=min(min1,sum[i-m]);
if(sum[i]>=min1){
return 1;
}
}
return 0;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>arr[i];
}
double l=1,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;
}
“如果返回1那么我们就继续增大我们的选择。否则我们就缩小答案范围”
你好,打扰了,请问这句话该怎么理解好啊?实在是没看懂代码中怎么在众多的解中,选出最优的哪个?