Median - 题解

标签与难度

标签: 动态规划, 构造, 实现难度: 1700

题目大意喵~

Nyahello~ 各位算法大师！今天我们遇到的这道题，就像是在玩一个猜数字游戏，不过是猜一整个序列，是不是很有趣呀，喵~?

事情是这样的：有一个神秘的整数序列 $a$ （长度为 $n$ ），我们并不知道它长什么样。但是，有人对它进行了一系列操作：对于从 $i=1$ 到 $n-2$ 的每一个位置，都取出了 $a_i, a_{i+1}, a_{i+2}$ 这三个相邻的数，计算出它们的中位数，并记作 $b_i$ 。

现在，我们只知道这个中位数序列 $b$ （长度为 $n-2$ ），我们的任务就是反向推理，找出任何一个可能的原始序列 $a$ 。如果找不到，就要告诉人家 "不行哦"（输出 -1）。

举个栗子：如果 $a = \{10, 40, 20, 50, 30\}$ ，那么：

$b_1 = \text{median}(a_1, a_2, a_3) = \text{median}(10, 40, 20) = 20$
$b_2 = \text{median}(a_2, a_3, a_4) = \text{median}(40, 20, 50) = 40$
$b_3 = \text{median}(a_3, a_4, a_5) = \text{median}(20, 50, 30) = 30$ 所以，如果输入是 $n=5$ 和 $b = \{20, 40, 30\}$ ，我们输出 $a = \{10, 40, 20, 50, 30\}$ 就是一个正确的答案啦！

解题思路分析

这道题是要我们从结果反推输入，这种问题通常都暗藏玄机，需要我们仔细观察，用我们猫咪一样敏锐的眼睛去发现线索，喵~！

关键的第一步：缩小 $a_i$ 的取值范围

我们完全不知道 $a_i$ 可以是哪些数，它们的范围是无限的吗？这可就难办啦！但是，让我们仔细看看中位数的定义。median(x, y, z) 的值必然是 $x, y, z$ 中的一个。

所以，对于 $b_i = \text{median}(a_i, a_{i+1}, a_{i+2})$ ，我们知道 $b_i$ 的值一定等于 $a_i, a_{i+1}, a_{i+2}$ 中的某一个。

这给了我们一个巨大的提示！反过来看，序列 $a$ 中的每一个元素 $a_i$ 都会作为输入，参与到几个中位数的计算中去。具体来说， $a_i$ 会影响到：

median(a_{i-2}, a_{i-1}, a_i)，也就是 $b_{i-2}$
median(a_{i-1}, a_i, a_{i+1})，也就是 $b_{i-1}$
median(a_i, a_{i+1}, a_{i+2})，也就是 $b_i$

既然 $a_i$ 是这三个中位数计算的输入之一，那么 $a_i$ 的值会不会就藏在对应的 $b$ 值里呢？这是一个非常合理的猜测！也就是说， $a_i$ 的可能取值，可以被限制在一个很小的集合里，即 $\{b_{i-2}, b_{i-1}, b_i\}$ 。

对于序列的边界，比如 $a_1$ ，它只参与了 $b_1$ 的计算。 $a_2$ 参与了 $b_1, b_2$ 的计算。为了方便处理这些边界情况，我们可以用一个叫做“哨兵”或者“填充”的小技巧。我们把给定的 $b$ 序列（长度为 $n-2$ ）两端扩展一下，比如把所有下标小于1的 $b$ 值都看作 $b_1$ ，所有下标大于 $n-2$ 的 $b$ 值都看作 $b_{n-2}$ 。这样，对于任何 $a_i$ ，我们都可以说它的候选值来自一个包含3个元素的集合啦！

第二步：动态规划出场！

既然每个 $a_i$ 只有 3 个候选值，问题就从无限可能变成了有限的选择了。这闻起来就像是动态规划的味道，喵~！

我们可以从左到右构建序列 $a$ 。当我们决定 $a_i$ 的值时，需要确保它和我们已经决定的 $a_{i-1}, a_{i-2}$ 能够正确地生成 $b_{i-2}$ 。这个依赖关系正是 DP 的用武之地。

状态定义: 让我们定义一个状态 dp[i][j][k]，它是一个布尔值，表示：是否存在一个合法的序列前缀 $a_1, \dots, a_i$ ，使得 $a_{i-1}$ 选的是它自己的第 j 个候选值，并且 $a_i$ 选的是它自己的第 k 个候选值。这里的 j 和 k 都是从 0 到 2 的索引。

状态转移: 我们想要求出 dp[i][j][k]。为了让这个状态为 true，必须存在一个来自上一步的合法状态。也就是说，我们要为 $a_{i-2}$ 找一个候选值（比如第 p 个），使得 dp[i-1][p][j] 为 true。

同时，这三个数的选择必须满足中位数的约束条件，也就是：

\text{median}(a_{i-2}, a_{i-1}, a_i) = b_{i-2}

把候选值代入就是：

\text{median}(\text{candidate}(i-2, p), \text{candidate}(i-1, j), \text{candidate}(i, k)) = b_{i-2}

如果这个条件满足，我们就可以从 dp[i-1][p][j] 转移到 dp[i][j][k]。

为了能最后把答案序列 $a$ 找出来，我们还需要一个 prev_choice[i][j][k] 数组，记录下当 $a_{i-1}$ 选第 j 个、 $a_i$ 选第 k 个候选值时，是哪个成功的 $a_{i-2}$ 的候选值索引 p 转移过来的。

基本流程:

预处理: 准备好每个 $a_i$ 的 3 个候选值。别忘了用填充技巧处理边界。
初始化: 第一个约束 $b_1$ 是由 $a_1, a_2, a_3$ 决定的。所以在 $i=3$ 之前，我们还没有任何约束。因此，我们可以认为 dp[2][j][k] 对所有 j, k 都为 true，表示 $a_1, a_2$ 的任意候选值组合都是一个合法的起点。
DP递推: 从 $i=3$ 到 $n$ ，我们用上面描述的状态转移方程，一层一层地计算 dp 表和 prev_choice 表。
寻找答案: DP结束后，检查所有 dp[n][j][k]。只要有一个为 true，就说明找到了一个解！
回溯构造: 从一个成功的 dp[n][j][k] 开始，利用 prev_choice 数组，像循着爪印一样倒着走，一步步确定 $a_n, a_{n-1}, \dots, a_1$ 的值。
如果所有 dp[n][j][k] 都为 false，那就说明无解，输出 -1。

这样，一个看似复杂的问题就被我们分解成清晰的小步骤啦！是不是感觉思路清晰多了呢？

代码实现

下面就是我根据这个思路，精心为大家准备的代码实现啦！注释很详细的哦，希望能帮到你，喵~

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

// 一个小小的辅助函数，用来求三个数的中位数，喵~
int get_median(int x, int y, int z) {
    if (x > y) std::swap(x, y);
    if (y > z) std::swap(y, z);
    if (x > y) std::swap(x, y);
    return y;
}

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> b(n - 1); // 使用 1-based indexing for b, b[1] to b[n-2]
    for (int i = 1; i <= n - 2; ++i) {
        std::cin >> b[i];
    }

    if (n <= 2) {
        // 如果 n 太小，直接输出1，因为没有b序列，任何a都行
        for (int i = 0; i < n; ++i) std::cout << "1 ";
        std::cout << "\n";
        return;
    }

    // --- 步骤 1: 准备候选值 ---
    // candidates[i][k] 存储 a_i 的第 k 个候选值 (k=0,1,2)
    std::vector<std::vector<int>> candidates(n + 1, std::vector<int>(3));
    for (int i = 1; i <= n; ++i) {
        // 用填充技巧处理边界，下标小于1的b看作b[1]，大于n-2的看作b[n-2]
        int b_im2 = (i - 2 < 1) ? b[1] : b[std::min(i - 2, n - 2)];
        int b_im1 = (i - 1 < 1) ? b[1] : b[std::min(i - 1, n - 2)];
        int b_i = (i < 1) ? b[1] : b[std::min(i, n - 2)];
        candidates[i][0] = b_im2;
        candidates[i][1] = b_im1;
        candidates[i][2] = b_i;
    }

    // --- 步骤 2 & 3: DP ---
    // dp[i][j][k]: 是否能构造到 a_i, 且 a_{i-1}用第j个候选值, a_i用第k个
    std::vector<std::vector<std::vector<bool>>> dp(n + 1, std::vector<std::vector<bool>>(3, std::vector<bool>(3, false)));
    // prev_choice[i][j][k]: 记录转移到 dp[i][j][k] 时 a_{i-2} 的候选值索引
    std::vector<std::vector<std::vector<int>>> prev_choice(n + 1, std::vector<std::vector<int>>(3, std::vector<int>(3, -1)));

    // 初始化：a_1 和 a_2 的选择不受任何 b 的约束，所以任意组合都行
    for (int j = 0; j < 3; ++j) {
        for (int k = 0; k < 3; ++k) {
            dp[2][j][k] = true;
        }
    }

    // DP 递推
    for (int i = 3; i <= n; ++i) {
        for (int j = 0; j < 3; ++j) { // a_{i-1} 的候选值索引
            for (int k = 0; k < 3; ++k) { // a_i 的候选值索引
                for (int p = 0; p < 3; ++p) { // a_{i-2} 的候选值索引
                    // 如果上一个状态是可达的
                    if (dp[i - 1][p][j]) {
                        int val_im2 = candidates[i - 2][p];
                        int val_im1 = candidates[i - 1][j];
                        int val_i = candidates[i][k];
                        
                        // 检查中位数约束
                        if (get_median(val_im2, val_im1, val_i) == b[i - 2]) {
                            dp[i][j][k] = true;
                            prev_choice[i][j][k] = p;
                            break; // 找到一个可行的 p 就行了，喵~
                        }
                    }
                }
            }
        }
    }

    // --- 步骤 4 & 5: 寻找答案并回溯 ---
    int final_j = -1, final_k = -1;
    for (int j = 0; j < 3; ++j) {
        for (int k = 0; k < 3; ++k) {
            if (dp[n][j][k]) {
                final_j = j;
                final_k = k;
                break;
            }
        }
        if (final_j != -1) break;
    }

    if (final_j == -1) {
        std::cout << "-1\n";
    } else {
        std::vector<int> a(n + 1);
        int current_k = final_k;
        int current_j = final_j;
        
        for (int i = n; i >= 1; --i) {
            if (i >= 2) {
                a[i] = candidates[i][current_k];
                if (i > 2) {
                    int p = prev_choice[i][current_j][current_k];
                    current_k = current_j;
                    current_j = p;
                } else { // i == 2
                    a[i-1] = candidates[i-1][current_j];
                }
            }
        }

        for (int i = 1; i <= n; ++i) {
            std::cout << a[i] << (i == n ? "" : " ");
        }
        std::cout << "\n";
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析

时间复杂度: $O(T \cdot N)$ ，其中 $T$ 是测试用例的数量， $N$ 是序列的长度。对于每个测试用例，我们有一个三层循环来填充DP表。循环的次数是 $N \times 3 \times 3 \times 3$ 。因为 3 是一个很小的常数，所以整体的时间复杂度是线性的，也就是 $O(N)$ 。我们只需要像小猫散步一样，从头到尾走一遍序列就可以啦！
空间复杂度: $O(N)$ 。我们主要使用了 candidates, dp 和 prev_choice 这三个数组。它们的大小都是 $N \times 3$ 或 $N \times 3 \times 3$ 。同样，因为 3 是常数，所以空间复杂度是 $O(N)$ 。我们需要一些额外的空间来记下我们的思考过程，但这个空间和问题规模成正比，非常合理！

知识点总结

这道题真是一次愉快的思维探险呢！我们来总结一下这次探险中学到的宝贝知识吧：

约束缩减: 面对看似无限可能的解空间时，要做的第一件事就是寻找题目中隐藏的约束条件。本题的关键突破口就是发现 $a_i$ 的值只能来自一个极小的候选集合。
动态规划 (DP): 当问题可以被分解成有重叠的子问题，并且子问题的解可以用来构建更大问题的解时，DP就是我们的超级武器！这里的状态定义（依赖于前两个元素的选择）是解决问题的核心。
路径记录与回溯: 很多DP问题不仅要求我们判断“是否可行”或计算“最优值”，还要求我们给出具体的方案。这时，在DP过程中额外记录下转移路径（比如用 prev_choice 数组），最后通过回溯来构造答案，是一个非常标准的技巧。
边界处理 (Padding/哨兵): 在处理序列问题时，边界情况（开头和结尾）常常需要特殊处理。使用“填充”或“哨兵”值，可以统一处理逻辑，让代码更简洁、更不容易出错，就像给我的爪子戴上柔软的手套一样，喵~

希望这篇题解能对你有所帮助！继续享受编程的乐趣吧，我们下次再见，喵~ 🐾

Median - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

关键的第一步：缩小 aia_iai​ 的取值范围 ​

第二步：动态规划出场！ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​