102. 最佳牛围栏--------------->二分,不定窗口
作者:
cyuyu
,
2022-05-08 19:41:37
,
所有人可见
,
阅读 178
//5000 2800为什么过不了呢?-------------->使用单纯前缀和,能过才怪,没看到窗口不固定
#include<iostream>
#include<cmath>
using namespace std;
const int N=100010;
typedef long long ll;
double a[N];
double s[N];
int n,m;
bool check(double mid){
ll sum=0;
for(int i=1;i<=n;i++){
s[i]=s[i-1]+a[i];
}
// ----------------大于m--------------------
// double mi=0;
//for(int i=m;i<=n;i++){
//就算我用现在末尾这个数减去前边和较小的那一个其实也是不可以的,我不能每次都取前边最小的那个值
/*
mi=min(mi,s[i-m]);
if(s[i]-mi>=0){
return true;
}
*/
//}
// --------------窗口小于m-----------------
int p=0;
for(int i=1;i<=n;i++){
double mi=a[p];//如果将平均值该为和,如果仍然是求平均值最大,mi=0
int t=max(0,i-m);
for(int j=t;j<i;j++){
mi=min(mi,s[j]);
if(s[i]-mi>=mid){
return true;
}
}
p++;
}
return false;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
double l=1;
double r=1e7;
double eps=1e-8;
while(r-l>eps){
double mid=(l+r)/2;
if(check(mid))
l=mid;
else
r=mid;
}
cout<<int(r*1000)<<endl;
return 0;
}
s[i]-s[j],保证s[j]每次取最小!