1 solutions
-
-1
#include<bits/stdc++.h> using namespace std; const int N=100001; int cow[N]; //牛的数量 double f[N]; //平均数的前缀和 int n,m; bool check(double av) { for(int i=1;i<=n;i++) { f[i]=f[i-1]+cow[i]-av;//平均值 } double minv=0;//最小值 for(int i=0,j=m;j<=n;i++,j++) { minv=min(minv,f[i]); //维护前i个的除去平均值的前缀和的最小值 if(f[j]>=minv) //f[j]-f[i]的大于等于0 { return true; //存在选择连续F个田地的平均值是大于等于av的 } } return false; //整个数组遍历完也找不到合适的解 } int main() { cin>>n>>m; for(int i=1;i<=n;i++) { cin>>cow[i]; } double l=0,r=2000; while(r-l>1e-5) { double mid=(r+l)/2.0; if(check(mid)) { l=mid;//说明平均值可以更大 } else r=mid; } printf("%d",int(r*1000)); return 0; }
- 1
Information
- ID
- 173
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 5
- Tags
- (None)
- # Submissions
- 5
- Accepted
- 4
- Uploaded By