测试点 $1\sim8$
首先，题目的操作即交换差分。
将答案变式：
\[\begin{aligned} n^2\cdot\dfrac1n\sum_{i=1}^n\left(a_i-\overline{a}\right)^2&=n\sum_{i=1}^n\left(a_i-\overline{a}\right)^2\\ &=n\sum_{i=1}^n\left(a_i-\dfrac1n\sum_{i=1}^na_i\right)^2\\ &=n\sum_{i=1}^n\left(a_i^2-2a_i\dfrac1n\sum_{i=1}^na_i+\left(\dfrac1n\sum_{i=1}^na_i\right)^2\right)\\ &=n\sum_{i=1}^na_i^2-2\left(\sum_{i=1}^na_i\right)^2+\left(\sum_{i=1}^na_i\right)^2\\ &=n\sum_{i=1}^na_i^2-\left(\sum_{i=1}^na_i\right)^2 \end{aligned}\]因此，求得差分 \(\textit{diff}_i=a_i-a_{i-1}\) 后，对 $\textit{diff}_2,\textit{diff}_3,\cdots,\textit{diff}_n$ 全排列，每次 $\mathcal O(n)$ 统计答案即可。
渐进时间复杂度上界为 $\mathcal O((n-1)!)$，可以通过测试点 $1\sim5$。但是注意到测试点 $6\sim8$ 的值域较小，因此本质不同的 $\textit{diff}_i$ 不多，仍然可以通过。
期望得分：$\text{32pts}$。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=1e4,V=600;
int n,a[N+1],diff[N+1];
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
diff[i]=a[i]-a[i-1];
}
sort(diff+2,diff+n+1);
int ans=2147483647;
do{
for(int i=1;i<=n;i++){
a[i]=a[i-1]+diff[i];
}
int pl=0;
for(int i=1;i<=n;i++){
pl+=a[i]*a[i];
}
pl*=n;
int sum=0;
for(int i=1;i<=n;i++){
sum+=a[i];
}
ans=min(ans,pl-sum*sum);
}while(next_permutation(diff+2,diff+n+1));
cout<<ans<<'\n';
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
测试点 $9\sim22$
交换差分的操作具有一个性质：最终方差最小时，差分 $\textit{diff}_2,\textit{diff}_3,\cdots,\textit{diff}_n$ 是单谷的。
即中间存在一个最小值 \(\textit{diff}_i\)，对于 $1<j<i$，差分单调不增，有 \(\textit{diff}_j\geq\textit{diff}_{j+1}\)；对于 $i<j$，差分单调不降，有 \(\textit{diff}_{j-1}\leq\textit{diff}_j\)。
证明
记 $\overline a$ 为 $a_1,a_2,\cdots,a_n$ 的平均值。假设差分单谷成立。
- 对于 $a_i<\overline a$ 的前半部分，可以发现差分单调递减时更优。因为这样会有更多元素接近于 $\overline a$。
- 对于 $\overline a<a_i$ 的后半部分，可以发现差分单调递增时更优。因为这样会有更多元素接近于 $\overline a$。
当差分不为单谷时，可以通过交换差分的方式，将其交换为单谷的形式，这样更优。
在此之后，便考虑 DP 求解。
为了便于 DP，重定义 \(\textit{diff}_i=a_{i+1}-a_i,\textit{pre}_i=\sum\limits_{j=1}^i\textit{diff}_j\)。
不妨令 \(\textit{diff}_1,\textit{diff}_2,\cdots,\textit{diff}_{n-1}\) 单调不降。
设 \(\textit{dp}_{i,j}\) 表示插入了 \(\textit{diff}_1,\textit{diff}_2,\cdots,\textit{diff}_{i-1}\) 后，使得 $\sum\limits_{k=1}^{i-1}a_k=j$ 的最小的 $\sum\limits_{k=1}^{i-1}a_k^2$。答案即：
\[\min\limits_{i=0}^{n\cdot a_n}\left(n\cdot\textit{dp}_{n,i}-i^2\right)\]显然有 DP 边界：
\[\textit{dp}_{1,0}=0\]考虑从左右两边分别插入 $\textit{diff}_i$，有：
\[\begin{aligned} \textit{dp}_{i+1,j+i\cdot\textit{diff}_i}&\leftarrow\min\left(\textit{dp}_{i+1,j+i\cdot\textit{diff}_i},\textit{dp}_{i,j}+2j\cdot\textit{diff}_i+i\cdot\textit{diff}_i^2\right)\\ \textit{dp}_{i+1,j+\textit{pre}_i}&\leftarrow\min\left(\textit{dp}_{i+1,j+\textit{pre}_i},\textit{dp}_{i,j}+\textit{pre}_i^2\right)\\ \end{aligned}\]时间复杂度：$\mathcal O\left(n^2V\right)$。滚动数组优化即可避免 MLE。
期望得分：$\text{88pts}$。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
constexpr const int N=1e4,V=600,Size=5e5;
constexpr const ll inf=0x3f3f3f3f3f3f3f3f;
int n,a[N+1],diff[N+1],pre[N+1];
ll dp[2][Size+1];
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<n;i++){
diff[i]=a[i+1]-a[i];
}
sort(diff+1,diff+n);
for(int i=1;i<n;i++){
pre[i]=pre[i-1]+diff[i];
}
memset(dp,0x3f,sizeof(dp));
bool mode=0;
dp[1][0]=0;
for(int i=1;i<n;i++){
mode=!mode;
memset(dp[!mode],0x3f,sizeof(dp[!mode]));
for(int j=0;j<=n*a[n];j++){
if(dp[mode][j]==inf){
continue;
}
dp[!mode][j+i*diff[i]]=min(dp[!mode][j+i*diff[i]],dp[mode][j] + 2ll*j*diff[i] + 1ll*i*diff[i]*diff[i]);
dp[!mode][j+pre[i]]=min(dp[!mode][j+pre[i]],dp[mode][j]+1ll*pre[i]*pre[i]);
}
}
ll ans=inf;
for(int i=0;i<=n*a[n];i++){
if(dp[!mode][i]==inf){
continue;
}
ans=min(ans,n*dp[!mode][i]-1ll*i*i);
}
cout<<ans<<'\n';
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
测试点 $23\sim25$
注意到当 $n=10^4$ 时，$\mathcal O\left(n^2V\right)$ 不再能被接受。
但是注意到此时 $V=50$ 较小，因此必然会有很多重复的 $a_i$，因此会有很多 $\textit{diff}_i=0$。对于这一部分无需进行转移，可以跳过。
因此可以做到 $\mathcal O\left(\min(n,V)nV\right)$ 的时间复杂度。
期望得分：$\text{100pts}$。
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
constexpr const int N=1e4,V=600,Size=5e5;
constexpr const ll inf=0x3f3f3f3f3f3f3f3f;
int n,a[N+1],diff[N+1],pre[N+1];
ll dp[2][Size+1];
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<n;i++){
diff[i]=a[i+1]-a[i];
}
sort(diff+1,diff+n);
for(int i=1;i<n;i++){
pre[i]=pre[i-1]+diff[i];
}
memset(dp,0x3f,sizeof(dp));
bool mode=0;
dp[1][0]=0;
for(int i=1;i<n;i++){
if(!diff[i]){
continue;
}
mode=!mode;
memset(dp[!mode],0x3f,sizeof(dp[!mode]));
for(int j=0;j<=n*a[n];j++){
if(dp[mode][j]==inf){
continue;
}
dp[!mode][j+i*diff[i]]=min(dp[!mode][j+i*diff[i]],dp[mode][j] + 2ll*j*diff[i] + 1ll*i*diff[i]*diff[i]);
dp[!mode][j+pre[i]]=min(dp[!mode][j+pre[i]],dp[mode][j]+1ll*pre[i]*pre[i]);
}
}
ll ans=inf;
for(int i=0;i<=n*a[n];i++){
if(dp[!mode][i]==inf){
continue;
}
ans=min(ans,n*dp[!mode][i]-1ll*i*i);
}
cout<<ans<<'\n';
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
