Moe's CF Life

喵~ 主人，你好呀！今天我们来看一道 Codeforces 上的有趣问题 C. Absolute Zero 呐。这道题看起来有点复杂，但只要我们一起分析，就能找到藏在里面的小鱼干哦！嘿嘿，跟着我的思路来吧！

题目大意

我们有一个整数数组 a，包含 n 个数字。我们可以执行一种操作，最多 40 次：

选择一个整数 x（0 <= x <= 10^9）。
对于数组中的每个元素 a_i，都用 |a_i - x| 来替换它。

我们的目标是通过一系列操作（最多 40 次），让数组里所有的元素都变成 0。如果可以做到，就输出操作次数和每次操作选的 x 值；如果不行，就输出 -1。

举个栗子，如果数组是 [4, 6, 8]，我们可以：

选 x = 6，数组变成 [|4-6|, |6-6|, |8-6|] = [2, 0, 2]。
再选 x = 1，数组变成 [|2-1|, |0-1|, |2-1|] = [1, 1, 1]。
最后选 x = 1，数组变成 [|1-1|, |1-1|, |1-1|] = [0, 0, 0]。这样就成功啦，喵~

解题思路

这道题的关键在于理解 |a_i - x| 这个操作会带来什么变化。我们的目标是全 0，而 0 是一个偶数。那我们不妨从奇偶性的角度来思考一下，说不定会有意外的发现哦！

关键性质：奇偶性

我们来分析一下操作对数字奇偶性的影响：

偶数 - 偶数 = 偶数
偶数 - 奇数 = 奇数
奇数 - 偶数 = 奇数
奇数 - 奇数 = 偶数

取绝对值并不会改变一个数的奇偶性。所以，|a_i - x| 的奇偶性和 a_i - x 的奇偶性是一样的。

假设我们选择了一个 x。

如果 x 是偶数：
- 如果 a_i 是偶数，a_i - x 是偶数。
- 如果 a_i 是奇数，a_i - x 是奇数。
- 也就是说，所有元素的奇偶性都不变。
如果 x 是奇数：
- 如果 a_i 是偶数，a_i - x 是奇数。
- 如果 a_i 是奇数，a_i - x 是偶数。
- 也就是说，所有元素的奇偶性都翻转了。

看到了吗，主人？一次操作，要么所有元素的奇偶性都不变，要么就一起翻转。这意味着，如果初始数组里既有奇数又有偶数，那么无论我们怎么操作，数组里永远都会同时存在奇数和偶数！

而我们的目标是让所有数都变成 0，0 是一个偶数。如果一开始数组里就有奇有偶，我们永远也无法让它们都变成偶数，更别提都变成 0 了。

所以，我们得出了第一个重要的结论：

如果初始数组中，非零元素的奇偶性不统一（即同时存在奇数和偶数），那么就不可能完成任务。这种情况下直接输出 -1 就好啦。

如何让数值变小？

好啦，现在我们知道，所有非零的数必须同为奇数或同为偶数。那么接下来的问题是，怎么选择 x 才能最快地让所有数都变成 0 呢？

我们的目标是让数组里的最大值不断变小，直到为 0。假设当前数组中的最大值是 max_val，最小值是 min_val。我们选择一个 x，新的数组中的最大值会是什么呢？新的最大值是 max(|a_i - x|)。为了让这个值尽可能小，一个非常经典和直观的想法是，让 x 位于 min_val 和 max_val 的正中间！

也就是选择 x = (min_val + max_val) / 2。

为什么这样选呢？喵~

min_val 会变成 |min_val - (min_val + max_val) / 2| = (max_val - min_val) / 2。
max_val 会变成 |max_val - (min_val + max_val) / 2| = (max_val - min_val) / 2。
对于任何在 min_val 和 max_val 之间的 a_i，|a_i - x| 的值都不会超过 (max_val - min_val) / 2。

所以，经过这次操作，新的最大值最多就是 (max_val - min_val) / 2。这使得数组中数值的范围（max_val - min_val）大约减半了！这样下去，最大值会很快趋近于 0。

因为初始 a_i 最大是 10^9，每次操作都让数值范围大致减半，所以操作次数会是 log_2(10^9) 级别，大约是 30 次，完全在 40 次的限制之内，太棒啦！

我们还需要确认一下，x = (min_val + max_val) / 2 这个操作会不会破坏我们之前发现的奇偶性统一的性质。因为我们已经保证了数组里所有数的奇偶性相同，所以 min_val 和 max_val 的奇偶性也相同。

奇数 + 奇数 = 偶数
偶数 + 偶数 = 偶数 所以 min_val + max_val 永远是偶数，那么 x = (min_val + max_val) / 2 就一定是个整数！既然 x 的奇偶性确定了，那么所有 |a_i - x| 的新奇偶性也会是统一的。性质完美保持！

算法总结

所以，我们的完整策略就是：

检查初始数组。如果所有数都已经是 0，那就不需要操作啦。
检查数组中所有非零数的奇偶性。如果既有奇数又有偶数，输出 -1。
如果可以通过，就进入一个循环，直到数组中所有数都变成 0： a. 找到当前数组的最大值 max_val 和最小值 min_val。 b. 计算 x = (min_val + max_val) / 2，并把这个 x 记录下来。 c. 对数组中每个 a_i，更新为 |a_i - x|。
最后，输出记录下来的操作次数和 x 序列。

这样，我们就能在有限的步数内解决问题啦，喵~

题解代码

这是根据上面的思路写出的 C++ 代码，我已经加上了可爱的注释哦！

cpp

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

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    bool all_zero = true;
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        if (a[i] != 0) {
            all_zero = false; // 检查是不是所有数都已经是0了
        }
    }

    // 如果一开始就都是0，那就不需要操作啦，喵~
    if (all_zero) {
        std::cout << 0 << "\n\n";
        return;
    }

    // 检查奇偶性是否统一
    int parity = a[0] % 2;
    for (int i = 1; i < n; ++i) {
        if (a[i] % 2 != parity) {
            // 哎呀，有奇数也有偶数，这是不可能完成的任务！
            std::cout << -1 << "\n";
            return;
        }
    }

    std::vector<int> ops; // 用来记录我们每次操作的 x
    while (true) {
        // 找到当前数组的最大值和最小值
        auto [min_it, max_it] = std::minmax_element(a.begin(), a.end());
        int min_val = *min_it;
        int max_val = *max_it;

        // 如果最大值已经是0了，说明所有数都变成0了，任务完成！
        if (max_val == 0) {
            break;
        }

        // 选择 x 为最大值和最小值的平均数
        int x_op = (min_val + max_val) / 2;
        ops.push_back(x_op); // 记录下这次的 x

        // 更新数组中的每一个数
        for (int& val : a) {
            val = std::abs(val - x_op);
        }
    }

    // 输出结果
    std::cout << ops.size() << "\n";
    if (!ops.empty()) {
        for (size_t i = 0; i < ops.size(); ++i) {
            std::cout << ops[i] << (i == ops.size() - 1 ? "" : " ");
        }
    }
    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;
}

知识点

这道题用到了几个很有趣的数学和算法思想呢，主人快来学习一下！

奇偶性分析 (Parity Analysis)
- 奇偶性是整数的一个基本属性。在很多和整数运算相关的题目里，分析奇偶性的变化是一个非常强大的工具。
- 就像这道题，我们通过分析 |a_i - x| 操作如何影响奇偶性，直接找到了一个判断无解的充要条件。这个发现是解题的突破口，喵！
贪心策略与中点选择 (Greedy Strategy and Midpoint Choice)
- 我们的解法在每一步都试图让情况变得“最好”，也就是让数组的最大值变得尽可能小。这种只关注当前最优解的策略就是一种贪心算法。
- 选择 x = (min_val + max_val) / 2 是一个经典的贪心选择。在几何上，这相当于在数轴上找到一个点 x，使得它到给定点集（a_1, a_2, ...）的最远距离最小。这个最优的点就是点集中最小和最大值的中点。
对数级收敛 (Logarithmic Convergence)
- 由于我们每次操作都让数值范围 (max_val - min_val) 大约减半，所以最大值会以指数速度下降。这种快速收敛的特性保证了我们可以在很少的步数内（对数级别）达到目标，满足了题目 40 次操作的限制。

好啦，这次的题解就到这里啦！希望我的讲解能帮到主人哦。如果还有不懂的地方，随时可以再来问我，喵~ >w<

题目大意 ​

解题思路 ​

关键性质：奇偶性 ​

如何让数值变小？ ​

算法总结 ​

题解代码 ​

知识点 ​