WUSTOJ 2597 XZX的游戏【水题?】

本文主要是介绍WUSTOJ 2597 XZX的游戏【水题?】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目来源：http://acm.wust.edu.cn/problem.php?id=2597&soj=0
在这里插入图片描述 ★大佬就绕道吧，这题真不难，就是有些细节需要格外注意~
☆这道题是WUSTACM 2019-3月赛的一道“水题”，我拿了一血（开森），比赛的时候WA了好多次，补题的时候还是WA了4次，所以这篇博客有感而发~

思路：

1：我们从最原始的思维开始，直接生硬的套用公式，直接循环求平均值，循环求方差，这种方法没错但肯定会TLE的，复杂度o(nm)，在这个级以上
2：稍微优化一下，用一个数组sum记录前N项和，平均值可以直接求出来，方差老规矩求，复杂度还是o(nm),比1优化了一点点而已
3：再用一个数组s记录前N项平方和，方差的公式可以拆开（字太丑了awa）
在这里插入图片描述
这时时间复杂度优化到了 o(n) 就不会超时了?
4：如果你输入的时候用的是cin ，那么恭喜还会超时233，scanf快些~

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
double f[maxn],sum[maxn],s[maxn];
int main()
{int n;while(cin>>n){sum[0]=0;s[0]=0;for(int i=1;i<=n;i++){scanf("%lf",&f[i]);sum[i]=sum[i-1]+f[i];s[i]=s[i-1]+f[i]*f[i];}int m;cin>>m;while(m--){int l,r;scanf("%d%d",&l,&r);double ave=(sum[r]-sum[l-1])/(r-l+1);double ans=(r-l+1)*ave*ave+s[r]-s[l-1]-2*ave*(sum[r]-sum[l-1]);printf("%.2f\n",ans/(r-l+1));}}return 0;
}