2016年湘潭邀请赛 xtu1249

本文主要是介绍2016年湘潭邀请赛 xtu1249，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Rolling Variance


Accepted : 73		Submit : 205
Time Limit : 3000 MS		Memory Limit : 65536 KB Special Judge

Rolling Variance

Bobo learnt that the variance of a sequence a1,a2,…,an is

\sum n i = 1 ( a i - a ¯ ) 2 n - 1 - - - - - - - - - - - - \sqrt

where

a ¯ = \sum n i = 1 a i n .

Bobo has a sequence a1,a2,…,an ,and he would like to find the variance of each consecutive subsequences of length m .Formally, the i -th ( 1≤i≤n−m+1 ) rolling variance ri is the variance of sequence {ai,ai+1,…,ai+m−1} .

Input

The input contains at most 30 sets. For each set:

The first line contains 2 integers n,m (2≤m≤n≤105) .

The second line contains n integers a1,a2,…,an ( |ai|≤100 ).

Output

For each set, (n−m+1) lines with floating numbers r1,r2,…,rn−m+1 .

Your answer will be considered correct if its absolute or relative error does not exceed 10−4 .

Sample Input

Sample Output

题解：

这个题目其实很简单，但是当年大一还是太年轻了没有做出了，过了一段时间来很快就搞定了，希望再接再厉

就是把分子展开，然后分三类进行计算，使用前缀数组进行维护就可以了，而且都不会超数据

#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;#define MAXN 100005
int a[MAXN];
int arr[MAXN],sum[MAXN];int main()
{int n,m;//freopen("in.txt","r",stdin);while(scanf("%d%d",&n,&m)!=EOF){sum[0]=arr[0]=0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);sum[i]=sum[i-1]+a[i];arr[i]=arr[i-1]+a[i]*a[i];}for(int i=m;i<=n;i++){double ans=0;double temp=(sum[i]-sum[i-m])/(double)m;ans+=temp*temp*m+arr[i]-arr[i-m];ans-=2*temp*(sum[i]-sum[i-m]);printf("%0.8lf\n",sqrt(ans/(m-1)));}}return 0;
}

这篇关于2016年湘潭邀请赛 xtu1249的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！