水题纪念|【51nod - 1098】最小方差（基础数学，公式化简，前缀和，积的前缀和）数学|前缀和

题干：
若x1,x2,x3……xn的平均数为k。则方差s^2 = 1/n * [(x1-k)^2+(x2-k)^2+…….+(xn-k)^2] 。方差即偏离平方的均值，称为标准差或均方差，方差描述波动程度。
给出M个数，从中找出N个数，使这N个数方差最小。
Input
第1行：2个数M,N，(M > N, M <= 10000)
第2 - M + 1行：M个数的具体值(0 <= Xi <= 10000)
Output
输出最小方差 * N的整数部分。
Input示例
5 3
1
2
3
4
5
Output示例
2
解题报告：
首先想到这题肯定是要排序的，方差就是稳定程度嘛，肯定相邻的两个数好过不相邻的两个数，然后我们进行公式化简：

文章图片

因为我们知道，数据范围是1e4，所以n^2的复杂度虽然也可以但是我们还有更优秀的nlogn的方法：排序用去了nlogn，所以其他的部分最好在o(n)内完成。而我们观察原公式后发现如果直接求的话，那每一次遍历都需要o(m)求一遍k，那就又成o(nm)复杂度了，和n^2是一个数量级的，肯定不行，所以我们考虑用
文章图片
这一条性质巧妙的把k约掉，发现得出的这两项刚好满足前缀和类性质，于是可以o(1)查询了，然后o(n-m)遍历一遍，就可以出答案了。

下面上代码：

#include #define ll long long using namespace std; const int MAXN = 1e4+5; ll a[MAXN], sum[MAXN], summ[MAXN]; int main() { int n,m; cin>>n>>m; for(int i=1; i<=n; i++) { scanf("%lld",&a[i]); } sort(a+1, a+1+n); sum[0] = summ[0] = 0; for(int i=1; i<=n; i++) { sum[i] = sum[i-1] + a[i]; summ[i] = summ[i-1] + a[i]*a[i]; } double minn = (double)LLONG_MAX; for(int i=m; i<=n; i++) { double tmp = (summ[i]-summ[i-m])-1.0*(sum[i]-sum[i-m])*(sum[i]-sum[i-m])/m; minn = min(tmp,minn); } printf("%lld\n",(ll)floor(minn)); return 0; }

【水题纪念|【51nod - 1098】最小方差（基础数学，公式化简，前缀和，积的前缀和）】总结：由此我们也知道，不仅是值可以求前缀和，任何一个我们想知道的值，只要不带更新操作，都可以求前缀和。