噗叽组小朋友如何写出 NOIP T3？

· · 题解

本题解仅使用普及组知识点：搜索、剪枝、差分。

首先题意大家都懂。

我们不难发现，无论怎么交换差分，相邻两项的差值组成的集合是一样的。

对于这些差值，显然差值小的尽量接近平均值、尽量放中间，其他差值，从小到大放两边。

假设平均值为 x，对于中间元素必定尽量接近平均值，所以肯定会选择差值小的，而差值的排列对最左边、最右边的值没有影响。

基于这样的贪心，我们可以从小到大依次枚举每个差值放在最小差值的左边还是右边，最后依次递推出序列 a 求方差，时间复杂度 \mathcal{O}(n \times 2^n)，可得 48 分。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 1e4 + 5;
int n, ans = 1e18, a[N], d[N], q[2 * N];

// dfs：尝试把差分放到左边或右边 
void dfs(int step, int l, int r)
{
    if (step >= n) // 放完了 
    {
        int sum = a[1], t = a[1] * a[1] * n;
        for (int i = 2; i <= n; i++)
        {
            a[i] = a[i - 1] + q[l + i - 2]; // 当前数 = 前一个数 + 对应的差分
            sum += a[i]; // 累加总和
            t += a[i] * a[i] * n; // 累加平方和
        }
        t -= sum * sum;  // 减去总和的平方，得到真正的方差计算值
        ans = min(ans, t);
        return;
    } 
    q[l - 1] = d[step]; // 放左边 
    dfs(step + 1, l - 1, r);
    q[r + 1] = d[step]; // 放右边 
    dfs(step + 1, l, r + 1);
}

signed main()
{
    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++) d[i] = a[i + 1] - a[i];
    sort(d + 1, d + n);
    q[N] = d[1];  // 把最小的差分放在最中间作为起点
    dfs(2, N, N); // 从第 2 个差分开始，往左右两边填数
    cout << ans << "\n";
    return 0;
}

接下来，我们充分发挥人类智慧。

我们不难注意到，如数字很多但数值范围很小，差分序列范围更小。

假设有 n 个数字，数字大小不超过 m，那么不同非零差值的种数不超过 \sqrt{m}，因为差值加起来达到 m 了，差值为 0 的可能很多；而差值不为 0 的总个数不超过 m−1。

如何利用这些性质进行剪枝？

  1. 差值为 0 时，放左边和放右边的效果是一样的，我们统一放左边，这样就只需要爆搜差值不为 0 的部分，时间复杂度由 \mathcal{O}(n \times 2^n) 降低到了 \mathcal{O}(n \times 2^m)。

  2. 对于差值 d，如果有 k 个，它们放左边和放右边是顺序无关的，我们可以指定顺序，先放左边，再放右边，避免重复。这样每一种差值的爆搜复杂度都由 \mathcal{O}(2^k) 降低到了 \mathcal{O}(k)。

在爆搜基础上，加上这两个剪枝，即可通过本题。

::::info[时间复杂度] 以下内容来自 DeepSeek：

该代码的时间复杂度为：

\mathcal O\left(n\log n + n \prod_{v>d_1}(c_v+1)\right)

这里 d_1 是排序后的最小差分，c_v 是差分值 v 在原差分序列中出现的次数。

若 d_1=0，则 v 遍历所有非零差分值；若 d_1>0，则 v 遍历除 d_1 以外的不同差分值。

::::

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 1e4 + 5;
int n, ans = 1e18, a[N], d[N], q[2 * N];

// dfs：尝试把差分放到左边或右边
void dfs(int step, int l, int r)
{
    if (step >= n) // 放完了 
    {
        int sum = a[1], t = a[1] * a[1] * n;
        for (int i = 2; i <= n; i++)
        {
            a[i] = a[i - 1] + q[l + i - 2]; // 当前数 = 前一个数 + 对应的差分
            sum += a[i]; // 累加总和
            t += a[i] * a[i] * n; // 累加平方和
        }
        t -= sum * sum;  // 减去总和的平方，得到真正的方差计算值
        ans = min(ans, t);
        return;
    } 
    // 剪枝 1：如果差分为 0，放左放右结果一样，只搜一次即可
    if (!d[step]) q[l - 1] = d[step], dfs(step + 1, l - 1, r);
    else 
    {
        // 剪枝 2：优先放左边，如果和右边边界值不同才搜，避免重复的对称状态
        if (d[step] != q[r]) q[l - 1] = d[step], dfs(step + 1, l - 1, r);
        q[r + 1] = d[step]; // 放右边
        dfs(step + 1, l, r + 1);
    }
}

signed main()
{
    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++) d[i] = a[i + 1] - a[i];
    sort(d + 1, d + n);
    q[N] = d[1];  // 把最小的差分放在最中间作为起点
    dfs(2, N, N); // 从第 2 个差分开始，往左右两边填数
    cout << ans << "\n";
    return 0;
}