题目描述

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

输入格式：

N+1行，
第一行两个整数n和m
接下来n行，每行一个整数a[i],表示序列第i个数字

输出格式：

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

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

6500

题解：

二分

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
LL n, m;
LL num[100050];
LL ls[100050];
bool check(LL x)
{
    LL minn = 2147483640;
    ls[0] = 0, ls[1] = 0;
    for (int i = 1; i <= n; i++)
        ls[i] = ls[i-1] + num[i] - x;
    for (int i = m; i <= n; i++)
    {
        minn = min (minn, ls[i-m]);
        if (ls[i] >= minn)
            return 1;
    }
    return 0;
}
int main()
{
    LL maxx = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        scanf("%d", &num[i]), num[i] *= 10000, maxx = max(maxx, num[i]);
    LL l = 0, r = maxx;
    while (r - l > 1)
    {
        LL mid = (l + r) / 2;
        if (check(mid))
            l = mid;
        else
            r = mid;
    }
    if (check(r))
        cout << r / 10;
    else
        cout << l / 10;
    return 0;
}