感觉很难想
方差
思路
其实就是求 $Ans = n\sum a_i^2 - sum^2$ ，的最小值，其中 $sum$ 是 $a_i$ 的和
操作是任意选择一个正整数 $1 < i < n$，将 $a_i$ 变为 $a_{i - 1} + a_{i + 1} - a_i$ ，这不好处理，考虑差分，发现操作其实就是把差分数组中相邻两个数 swap 一下（差分数组中只有 $n - 1$ 个数， $b_i = a_{i + 1} - a_i$ ），还有一个性质，就是无论如何操作， $a_i$ 都是单调的
由于方差要最小，不难发现差分数组应该是单谷的，而谷底的数就是最接近于平均数的，因为每个数与谷底的数差就是两个下标之间的 $b_i$ 之和，所以当然是让小的数多算更优
对 $b_i$ 排序并求其前缀和 $s_i$ ，考虑 dp ，令 $f[i, j]$ 表示“把 $b$ 中前 $i$ 个数放好，当前数组 $a$ 和为 $j$ 的最小方差”，决策就是把 $b_i$ 放在左边或者右边，为了省空间用类似背包的倒序循环压掉第一维，有方程：
$$
\begin{aligned}
& f[j + i * b[i]] \gets f[j] + 2 * j * b[i] + i * b[i]^2 \\
& f[j + s[i]] \gets f[j] + s[i]^2
\end{aligned}
$$
注意开 long long
代码
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
| #include <bits/stdc++.h>
#define FF std::function
using LL = long long;
const int N = 1e4 + 100, NA = 5e5 + 100;
const LL INF = 0x7ffffffffffffffLL;
int n;
LL a[N], b[N], s[N], f[NA], ans = INF, mx;
int main()
{
FF<void(LL&, LL)> chkmin = [&](LL &x, LL y){ if (y < x) x = y; };
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]), mx = std::max(mx, a[i]);
for (int i = 1; i < n; ++i) b[i] = a[i + 1] - a[i];
std::fill(f + 1, f + mx * n + 1, INF);
f[0] = s[0] = mx = 0;
std::sort(b + 1, b + n);
for (int i = 1; i < n; ++i) s[i] = s[i - 1] + b[i];
for (int i = 1; i < n; ++i) if (b[i])
for (int j = mx; ~j; --j) if (f[j] != INF)
{
chkmin(f[j + i * b[i]], f[j] + ((j * b[i]) << 1) + i * b[i] * b[i]);
chkmin(f[j + s[i]], f[j] + s[i] * s[i]);
mx = std::max(mx, std::max(j + i * b[i], j + s[i]));
f[j] = INF;
}
for (int j = 0; j <= mx; ++j) if (f[j] < INF) chkmin(ans, n * f[j] - LL(j) * j);
printf("%lld\n", ans);
return 0;
}
|