在一维坐标轴上给出n个点，第i个点坐标为\(x_i\),现在你可以任意移动k个点的，最小化它们的方差，\(n\leq 50000\)。
设\(\bar{x}=\frac{\sum_{i=1}^nx_i}{n}\),容易知道方差为
\[\sum_{i=1}^n(x_i-\bar{x})^2=\sum_{i=1}^nx_i^2-n\bar{x}^2\]
对于只移动一个点坐标x来看，显然可以看成一个二次函数，即
\(f(x)=\sum_{i=1}^n{x_i}^2-n\bar{x}^2\)
因为化简过于复杂,对它进行求导，这样与x无关的项都可以丢掉了
\[f(x)'=(\sum_{i=1}^n{x_i}^2-n\bar{x}^2)'=2x-n(\bar{x}^2)'=2x-n2\bar{x}(\bar{x})'=\]
\[2x-2\bar{x}(\sum_{i=1}^nx_i)'=2x-2\bar{x}\]
容易知道随着x的增加，这个导函数是在单调递增的，因此它存在最小值，显然是在驻点处取到，故令\(f(x)'=0\)，有
\(x=\bar{x}\Rightarrow x=\frac{\sum_{i=1}^nx_i-x}{n-1}\)
于是对于只动一个坐标x而言，x取到除x以外的点的平均值所在的点就是答案，我们还可以得到一个结论，往数的集合中加入它的平均数，不改变新的集合的平均数。
但是我们需要讨论k个点的情况，于是对于每个点\(x_i\)我们可以有(不妨假设这k个点为\(x_1,x_2,..,x_k\))，那么分别有
\[x_1=\frac{\sum_{i=1}^nx_i-x_1}{n-1},x_2=\frac{\sum_{i=1}^nx_i-x_2}{n-1}...\]
\[x_k=\frac{\sum_{i=1}^nx_i-x_k}{n-1}\]
累加起来有
\[(n-1)\sum_{i=1}^kx_i=k\sum_{i=1}^nx_i-\sum_{i=1}^kx_i\]
也就是
\[n\sum_{i=1}^kx_i=k\sum_{i=1}^nx_i\]
也就是
\[\frac{\sum_{i=1}^kx_i}{k}=\frac{\sum_{i=1}^nx_i}{n}\]
于是我们得到了k个要动的数的平均值恰好为n个数的平均值，继续变
\[n\sum_{i=1}^kx_i=k\sum_{i=1}^nx_i\Rightarrow n\sum_{i=1}^kx_i=k\sum_{i=1}^kx_i+k\sum_{i=k+1}^nx_i\]
\[(n-k)\sum_{i=1}^kx_i=k\sum_{i=k+1}^nx_i\]
也就是
\[\frac{\sum_{i=1}^kx_i}{k}=\frac{\sum_{i=k+1}^nx_i}{n-k}\]
整理起来也就有
\[\frac{\sum_{i=1}^kx_i}{k}=\frac{\sum_{i=k+1}^nx_i}{n-k}=\frac{\sum_{i=1}^nx_i}{n}\]
所以可以得出一个很棒的结论，向一个集合中加入若干个平均数为改个集合的平均数，平均数不变，原来的集合的平均数等于加进的平均数等于新集合的平均数，而且满足两个相等，可以推出三个相等。
现在考虑k个数的方差，方差显然转换成下式比较好研究
\[\sum_{i=1}^nx_i^2-n\bar{x}^2\]
其余n-k个数字是常量(包括平均数)，拆开有
\[\sum_{i=1}^kx_i^2+\sum_{i=k+1}^{n}x_i^2-n\bar{x}^2\]
于是要让整个式子最小化，也就是最小化
\[\sum_{i=1}^nx_i^2=x_1^2+x_2^2+...+x_k^2\]
根据均值不等式，容易知道最小化这个式子，要满足\(x_1=x_2=...=x_k\)。
而我们有\(\frac{x_1+x_2+...+x_k}{k}=\frac{kx_1}{k}=x_1=\bar{x}\),于是有
\[x_1=x_2=...=x_k=\bar{x}=\frac{\sum_{i=k+1}^{n-k}x_i}{n-k}\]
也就是对于这k个数字，我们只要都放到剩下的数字平均数所在位置即可，而根据方差定义式。
\[\sum_{i=1}^n(x_i-\bar{x})^2\]
容易知道，此时这k个数字所产生的影响为0,因为\(x_i=\bar{x}(i=1,2,...,k)\)
于是我们只要考虑剩下n-k个数字的方差即可，而根据方差的实际含义，数字的离散程度，于是剩下n-k个数字要尽可能集中，于是我们只需要将所有坐标排序，取连续的长度为\(n-k\)的区间，把它们的方差取max即可，为了快速求出方差，我们根据推广式
\[\sum_{i=1}^nx_i^2-n\bar{x}^2\]
而\(\bar{x}=\frac{\sum_{i=1}^nx_i}{n}\),因此我们只要维护平方的前缀和和普通的前缀和，带入这个式子计算，就可以做到\(O(1)\)查询区间的方差了，整个时间复杂度仅有\(O(n)\)。
参考代码：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define il inline
#define ri register
#define lb double
#define Size 50500
using namespace std;
lb a[Size],sum[Size],sum2[Size];
int main(){
int lsy,n,k;scanf("%d",&lsy);
while(lsy--){
scanf("%d%d",&n,&k);
for(int i(1);i<=n;++i)
scanf("%lf",&a[i]);
if(n==k){printf("%.11lf\n",(lb)0);continue;}
sort(a+1,a+n+1);lb ans(1e100);k=n-k;
for(int i(1);i<=n;++i)
sum[i]=sum[i-1]+a[i],
sum2[i]=sum2[i-1]+a[i]*a[i];
for(int i(k);i<=n;++i)
ans=min(ans,sum2[i]-sum2[i-k]-k*pow((sum[i]-sum[i-k])/k,2));
printf("%.11lf\n",ans);
}
return 0;
}原文：https://www.cnblogs.com/a1b3c7d9/p/11408652.html