題目的意思就是說(shuō)，選一個(gè)大于等于F的窗口使其平均值最大。
那么求去掉平均值后的前綴和。
故如果存在一個(gè)大于等于F的區(qū)間使得 s[r]-s[l-1]>=0 說(shuō)明就是存在的

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; double a[N],s[N]; int n,m; bool check(double avg) {for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i]-avg;double ans=1e9;for(int i=0,j=m;j<=n;j++,i++){ans=min(ans,s[i]);//最小的左端點(diǎn)if(s[j]>=ans) return true;}return false; } int main(void) {cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];double l=0,r=2000;while(r-l>1e-8){double mid=(l+r)/2;if(check(mid)) l=mid;else r=mid;}printf("%d",int(r*1000));return 0; }

總結(jié)

以上是生活随笔為你收集整理的102. 最佳牛围栏【二分 / 思维 不错】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。