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;
}
总结
前缀和很重要
