- // 意是在一个数组里, 寻找一段连续和, 使其平均和最大, 但是长度不能小于 F,
- // 首先可以看出是满足单调性的, 但是怎么二分呢,
- // 我们先枚举一个可能的数.
- // 然后数组里的值全部减去这个值 (结果会有正有负),
- // 那么我们就看是否存一段长度大于等于 F, 且和为正. 对于此的判断, 可谓经典, 见代码.
- #include <stdio.h>
- #include <string.h>
- #include <iostream>
- #include <stdlib.h>
- #include <algorithm>
- using namespace std;
- double a[100005] , b[100005], c[100005];
- int main(){
- int n, f;
- cin>>n>>f;
- for(int i=1;i<=n;i++){
- scanf("%lf",a+i);
- }
- double eps = 1e-5;
- double l = -1e6, r = 1e6, mid;
- while(r-l>eps){
- c[0] = 0;
- mid = (l+r)/2.0;
- for(int i=1;i<=n;i++){
- b[i] = a[i] - mid;
- c[i] = c[i-1] + b[i];
- // cout<<"c[i] ="<<c[i]<<endl;
- }
- double maxn = -1e6, minn = 1e6;
- for(int i=f;i<=n;i++){
- // 左边最小值
- minn = min(minn,c[i-f]);
- // 除去左边, 右边一直变化的最大值
- maxn = max(maxn,c[i]-minn);
- }
- // cout<<"maxn ="<<maxn<<endl;
- if(maxn> 0)
- l = mid;
- else
- r = mid;
- }
- cout<<(int)(r*1000)<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2978890.html