K題
題目大意
題目鏈接
給你一個(gè)大小為n的數(shù)組a挟纱，和數(shù)字k罩句，求數(shù)組a中大小大于等于k的子數(shù)組的最大平均值
分析
先用一個(gè)循環(huán)來(lái)遍歷子數(shù)組的頭部，注意循環(huán)結(jié)束的條件估脆，i<=n-k殊轴。再用一個(gè)循環(huán)來(lái)遍歷子數(shù)組的尾部，對(duì)于每一個(gè)子數(shù)組袒炉，求出它的平均值旁理，并不斷更新，存儲(chǔ)最大的平均值我磁。但注意到題目中n和k的數(shù)據(jù)都比較大孽文，在代碼1中每次都去遍歷子數(shù)組來(lái)求和驻襟，最終導(dǎo)致在第13個(gè)測(cè)試數(shù)據(jù)中就超時(shí)了，所以這道題就要用到前綴和來(lái)計(jì)算芋哭，在輸入數(shù)據(jù)的時(shí)候就用另外一個(gè)數(shù)組來(lái)存儲(chǔ)前i個(gè)數(shù)據(jù)的和沉衣，這樣在求子數(shù)組和的時(shí)候就可以用sum=result[j+1]-result[i]直接求出和，簡(jiǎn)化了復(fù)雜度减牺。
代碼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;
}
總結(jié)
前綴和很重要
