K题

题目大意

题目链接
给你一个大小为n的数组a，和数字k，求数组a中大小大于等于k的子数组的最大平均值

分析

先用一个循环来遍历子数组的头部，注意循环结束的条件，i<=n-k。再用一个循环来遍历子数组的尾部，对于每一个子数组，求出它的平均值，并不断更新，存储最大的平均值。但注意到题目中n和k的数据都比较大，在代码1中每次都去遍历子数组来求和，最终导致在第13个测试数据中就超时了，所以这道题就要用到前缀和来计算，在输入数据的时候就用另外一个数组来存储前i个数据的和，这样在求子数组和的时候就可以用sum=result[j+1]-result[i]直接求出和，简化了复杂度。

代码1

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
#define MAX_N 5000+5
using namespace std;
int main(int argc, char const *argv[])
{
    int n,k;
    int number[MAX_N];
    double res1,res2=0;
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&number[i]);
    }
    for(int i=0;i<=n-k;i++)
    {
        for(int j=i+k-1;j<n;j++)
        {
            double sum=0;
            for(int m=i;m<=j;m++)
            {
                sum+=number[m];
            }
            res1=sum/(j-i+1);
            if(res1>res2)
                res2=res1;
        }
    }
    printf("%.15llf\n",res2);
    return 0;
}

代码2

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
#define MAX_N 5000+5
using namespace std;
int main(int argc, char const *argv[])
{
    int n,k;
    int number[MAX_N];
    int result[MAX_N];
    result[0]=0;
    double res1,res2=0;
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&number[i]);
        result[i+1]=result[i]+number[i];
    }
    for(int i=0;i<=n-k;i++)
    {
        for(int j=i+k-1;j<n;j++)
        {
            double sum=result[j+1]-result[i];
            res1=sum/(j-i+1);
            if(res1>res2)
                res2=res1;
        }
    }
    printf("%.15llf\n",res2);
    return 0;
}

总结
前缀和很重要