[NOIP2021] 方差题解

· · 题解

### 想法 首先列一个数轴，手玩一把数据，容易发现变化后的点到左边的点的距离等于原先的点到右边的距离，可以看出操作的实质就是将**差分数组交换**。 然后求最后答案的公式： $$n \times \sum_{i=1}^{n}{(a_i-\overline{a})^2}=n \times \sum_{i=1}^{n}{(a_i^2-2 \times a_i \times \overline{a}+\overline{a}^2)}$$ $$=n \times \sum_{i=1}^{n}a_i^2-2 \times (\sum_{i=1}^{n}a_i)^2+(\sum_{i=1}^{n}a_i)^2$$ $$=n \times \sum_{i=1}^{n}a_i^2-(\sum_{i=1}^{n}a_i)^2$$ 有一个重要的性质，那么就是**交换后的差分数组成单谷**。 ### 证明单谷 从感性的角度很好理解，但我们还是要从理性去证明。 考虑一项 $a_i$ 增加了 $d$ 之后的变化。 我们令 $n \times \sum_{i=1}^{n}a_i^2$ 为 $T$ ， $\sum_{i=1}^{n}a_i$ 为 $S$ ， 则: $$T \rightarrow T+n \times (2 \times a_i \times d+d^2) $$ $$S^2 \rightarrow (S+d)^2 =S^2+2 \times S \times d+d^2$$ $T$ 的增量为 $n \times (2 \times a_i \times d+d^2)$ ，$S$ 的增量为 $2 \times S \times d+d^2

要满足改变后的结果减小，必须保证

n \times (2 \times a_i \times d+d^2) < 2 \times S \times d+d^2

把 S 的值化开，因为是不等式，所以要讨论 d 的正负。

考虑交换两个相邻数组的差分值，即 d=d_{i+1}-d_i

考虑当 d > 0 时，也即是 d_{i+1} > d_i 时，两边同除以 n \times d , 原式就化为 ：

2 \times a_i+d < 2 \times \overline{a} + \frac{d}{n}

这个时候因为 d > 0 , 要满足这个柿子成立再交换，很明显有 a_i > \overline{a} 才满足这个式子不成立，即在最优情况不交换，也即是在 \overline{a} 之后的所有 a_i 的最优结构即是单调递增的。

考虑当 d < 0 时，也即是 d_{i+1} < d_i 时 , 两边同除以 n \times d , 原式就化为 ：

2 \times a_i+d > 2 \times \overline{a} + \frac{d}{n}

这个时候因为 d < 0 , 要满足这个柿子成立再交换，很明显有 a_i < \overline{a} 才满足这个式子不成立，即在最优情况不交换，也即是在 \overline{a} 之前的所有 a_i 的最优结构即是单调递减的。

注意这个时候的 \overline{a} 指的是原本的 \overline{a} ,在其调整后会变化，但调整前此刻的大小不变，这很好的告诉了我们：

最优解的差分数组必定是成单谷状的。

做法

证明了这样的一个优秀的性质之后，一切都变得好办了。

然后考虑维护单谷，先对差分数组进行排序，也即是每一个 dif_i 可以插到现单谷的最前面或者最后面，这样就完美地维护了单谷的性质。

然后发现这玩意儿可以直接 dp ，我们令 dp_{i,s} 为排序后前 i 个差分数组交换，a_i的和为 s 的最小平方和，于是我们就有:

后插柿子：

\mathit{dp}_{i,s+\sum_{j=1}^{i}dif_j} = min(\mathit{dp}_{i-1,s} + \sum_{j=1}^{i}dif_j \times \sum_{j=1}^{i}dif_j)

前插柿子：

\mathit{dp}_{i,s+dif_i*i} = min(\mathit{dp}_{i-1,s} + 2 \times s \times dif_i +i \times dif_i \times dif_i)

这两个柿子还是比较好理解的。

同时我们发现下一个 dif_i 的插入只与上一维的 dp 值有关，于是就可以直接滚动起来，对于后插柿子可以直接用前缀和维护。

但是这样的时间复杂度不就是 O(n^2*V) 的了么？？？

但仔细想想，我们可以对前面多个 dif_i==0 进行调整，那么这个时候原本剩下的数只剩下了 V 的大小，也即是第一维只用遍历 V 次，时间复杂度也即是 O(n*V^2) 的。

于是就写出了代码，巨好写：

#include<bits/stdc++.h>
#define int long long
#define Debug if(false) 
#define rnt register int
using namespace std;
const int maxn=10100,inf=2e9;
inline int read()
{
    int x=0,f=1;char c;
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-f;
    for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    return x*f;
}
int a[maxn],dif[maxn],sum[maxn],n=read();
int dp[2][500010],maxa;
signed main()
{
    for(rnt i=1;i<=n;i++) a[i]=read();
    for(rnt i=1;i<n;i++) dif[i]=a[i+1]-a[i];
    sort(dif+1,dif+n),maxa=a[n];int cnt0=1;
    for(rnt i=1;i<n;i++) if(!dif[i]) cnt0++;
    for(rnt i=1;i<n;i++) sum[i]=sum[i-1]+dif[i];
    int now=0,las=1,lim=maxa*n;
    for(rnt i=0;i<=lim;i++) dp[now][i]=inf; //初始全都设为inf 
    dp[now][dif[cnt0]]=dif[cnt0]*dif[cnt0]; //首值放尾 
    dp[now][dif[cnt0]*cnt0]=dif[cnt0]*dif[cnt0]*cnt0; //首值放头 
    for(rnt i=cnt0+1;i<n;i++)
    {
        now^=1,las^=1;
        for(rnt s=0;s<=lim;s++) dp[now][s]=inf;
        for(rnt s=0;s<=lim;s++)
        {
            if(dp[las][s]==inf) continue;
            dp[now][s+dif[i]*i]=min(dp[now][s+dif[i]*i],dp[las][s]+2*s*dif[i]+dif[i]*dif[i]*i); //放头
            dp[now][s+sum[i]]=min(dp[now][s+sum[i]],dp[las][s]+sum[i]*sum[i]); //放尾 
        }
    }
    int ans=inf;
    for(rnt i=0;i<=maxa*n;i++)
        if(dp[now][i]!=inf) ans=min(ans,n*dp[now][i]-i*i);
    cout << ans << endl;
    return 0;
}

总结

首先想到差分必须有一定的手玩技巧。其次就是重要的性质单谷。

这道题想到单谷可能很简单，但是在证明的时候总是差那么一点。我认为此题的思维难度还是比较高的，至少对于我这种菜鸡来说。