題目鏈接：點擊查看

題目大意：給出n個正整數，求一個平均數最大的、長度不小于L的連續子段

題目分析：因為這個題目的答案滿足二分的性質，也就是若二分的平均數小于答案，則更小的平均數肯定都滿足答案(因為這個連續子段的平均值肯定大于那些答案)，如果二分的平均數大于答案，則更大的平均數肯定都不滿足答案(同上)，所以我們可以直接二分平均值作為答案，現在問題轉換成了該怎么判斷當前二分的答案是否滿足條件，也就是判斷是否至少存在一個長度不小于L的連續子段，滿足平均數大于等于當前答案

到了這里，我們千萬不能理解為求長度不小于L的最大連續子段，因為都是正整數，所以最大連續子段肯定是整個序列的sum和，因為答案要的是平均值，子段和大的序列的平均值不一定大，因為兩者之間沒有直接的線性關系，所以我們轉換一下思路，可以預處理一個輔助數組，讓該輔助數組中儲存一下原數組每一項減去平均值后的數

現在問題就轉換為了：是否存在一個長度不小于L的連續子段，滿足權值和大于0，因為若權值和大于0的話，那么就說明當前這個子段的平均值大于二分的答案，返回true即可，否則返回false，換句話說，對于處理后的數組求一下最大連續子段和就好了

其實寫到這里我突然想到能不能直接求解呢？就是求出長度不小于L的連續子段平均值最大的值，這樣答案就出來了啊，但轉念一想，直接求的時間復雜度數n*n，需要用到雙指針枚舉每一個子段，在這個題目中肯定會超時，所以選擇用二分的方法將時間復雜度下降為nlogn

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const double eps=1e-5;const int N=1e5+100;int n,m;double a[N],sum[N];bool check(double x) {for(int i=1;i<=n;i++)//維護前綴和為a[i]-averagesum[i]=sum[i-1]+(a[i]-x);double mmin=1e10;double ans=-1e10;for(int i=m;i<=n;i++)//最大連續子段和{mmin=min(mmin,sum[i-m]);ans=max(ans,sum[i]-mmin);}return ans>=0;//判斷答案是否為非負數 }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);while(scanf("%d%d",&n,&m)!=EOF){for(int i=1;i<=n;i++)scanf("%lf",a+i);double l=0,r=1e10;while(abs(l-r)>=eps){double mid=(l+r)/2;if(check(mid))l=mid;elser=mid;}printf("%d\n",int(r*1000));}return 0; }

?

總結

以上是生活随笔為你收集整理的POJ - 2018 Best Cow Fences(二分+最长连续子段和)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。