题目描述

给一个长度为 $n$ 的数列，我们需要找出该数列的一个子串，使得子串平均数最大化，并且子串长度 $\ge m$。

输入格式

第一行两个整数 $n$ 和 $m$。

接下来 $n$ 行，每行一个整数 $a_i$，表示序列第 $i$ 个数字。

输出格式

一个整数，表示最大平均数的 $1000$ 倍，如果末尾有小数，直接舍去，不要用四舍五入求整。

输入输出样例

输入 #1

10 6
6
4
2
10
3
8
5
9
4
1

输出 #1

6500

说明/提示

• 对于 $60\%$ 的数据，保证 $m\le n\le 10^4$
• 对于 $100\%$ 的数据，保证 $1 \leq m\le n\le 10^5$，$0\le a_i\le2000$。

分析

显然这是一个“最小值最大”的问题，所以我们要通过二分来枚举平均值，再寻找字段和较大的字段，代入平均值判断是否成立，不成立则将右端向左，成立则将左端向右，使两个端点不断相互逼近最优解即可得到答案。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
double a[100001],sum[100001],b[100001];
double eps=1e-5,l=-1e6,r=1e6;
double min(double x,double y){
    if(x>y)return y;else return x;
}
double max(double x,double y){
    if(x<y)return y;else return x;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    while(r-l>eps){
        double mid = (l+r)/2;
        double maxx=-1e10,minn=1e10;
        for(int i=1;i<=n;i++)b[i]=a[i]-mid;
        for(int i=1;i<=n;i++)sum[i]=sum[i-1]+b[i];
        for(int i=m;i<=n;i++){ 
            minn=(double)min(minn,sum[i-m]);
            maxx=(double)max(maxx,sum[i]-minn);
        }
        if(maxx>0)l=mid;else r=mid;
    }
    cout<<int(r*1000);
    return 0;
}