Moe's CF Life

喵~ 各位算法大师们好呀！咱是乃们的猫娘小助手，今天又要和大家一起解决一道可爱的算法题啦！这次的问题是 Codeforces 上的 1834A - Unit Array，一个关于 -1 和 1 的小游戏。别看它简单，里面可藏着一些有趣的逻辑哦。那么，就让咱带大家一步步解开这个谜题吧，喵！

题目大意 (Problem Analysis)

这道题给了我们一个只包含 -1 和 1 的数组 a。我们的任务是，通过最少的操作次数，让这个数组变得“好”。

一个“好”的数组需要同时满足两个条件，缺一不可哦：

和非负 (Sum >= 0): 数组里所有数字加起来的总和，必须大于或等于 0。
积为一 (Product = 1): 数组里所有数字乘起来的总积，必须等于 1。

我们可以进行的操作是：选择数组里的任意一个元素，把它变成相反数。也就是说，-1 可以变成 1，1 也可以变成 -1。

那么问题来了，最少需要多少次这样的操作，才能让数组同时满足这两个条件呢？

举个栗子：如果数组是 [-1, -1, 1, -1]，它的和是 -2，积是 -1，两个条件都不满足。但如果我们把第一个 -1 变成 1，数组就成了 [1, -1, 1, -1]。这时候，和是 0，积是 1，哇！两个条件都满足了，而且我们只用了一次操作，是不是很棒呀！

解题思路 (Solution Approach)

要用最少的操作次数达成目标，我们就得想个最聪明的办法，喵！这种求最优解的问题，通常可以试试贪心策略。我们来分析一下这两个条件，看看怎么下手最划算。

关于“和非负” 数组里只有 1 和 -1。假设有 pos_count 个 1 和 neg_count 个 -1，那么数组的总和就是 pos_count - neg_count。要让 pos_count - neg_count >= 0，就意味着 1 的数量必须大于或等于 -1 的数量。因为数组总长度是 n，即 pos_count + neg_count = n，所以这个条件等价于 -1 的数量 neg_count 不能超过数组长度的一半，也就是 neg_count <= n / 2。
关于“积为一” 要让一堆 1 和 -1 的乘积是 1，这只取决于 -1 的数量。学过数学的我们都知道，只有偶数个 -1 相乘，结果才会是 1。所以，这个条件等价于 -1 的数量 neg_count 必须是偶数。

现在我们有两个目标：

目标A: neg_count <= n / 2
目标B: neg_count 是偶数

哪一个更重要呢？当然是目标A啦！因为如果我们有很多很多的 -1，比如 n=5 时有 4 个 -1，那总和肯定是负的。为了让总和变正，我们唯一的选择就是把 -1 变成 1。这样做不仅能增加总和，还能减少 -1 的数量，简直一举两得，喵！

所以，我们的贪心策略就来啦：

第一步：优先满足“和非负”条件。

我们先数一下数组里有多少个 -1，记作 neg_count。如果 neg_count > n / 2，说明 -1 太多了，总和肯定是负的。我们必须把一些 -1 变成 1。为了操作次数最少，我们不多不少，就翻转 neg_count - (n / 2) 个 -1。这样，-1 的数量就降到了 n / 2（这里是整除哦），刚好满足了和非负的条件。这些操作是必须的，我们把操作次数累加起来。

第二步：在满足第一步的基础上，满足“积为一”条件。

经过第一步，我们保证了 -1 的数量不会超过 n / 2。现在我们来看看 -1 的数量是不是偶数。

如果此时 neg_count 是偶数，那太棒了！两个条件都满足了，我们不需要再做任何事了，喵~
如果此时 neg_count 是奇数，那就不行啦，乘积会是 -1。我们必须再做些操作来改变 neg_count 的奇偶性。

怎么改变呢？最简单的办法就是再操作一次：

方案一：再把一个 -1 变成 1。 neg_count 会减 1，变成偶数。因为我们是减少 -1 的数量，总和会增加，所以“和非负”的条件依然满足。这需要 1 次操作。
方案二：把一个 1 变成 -1。 neg_count 会加 1，也变成偶数。但是！这样做会让 -1 的数量增加，可能会破坏我们在第一步好不容易满足的“和非负”条件。比如 n=4，第一步后我们让 neg_count 变成了 2。如果再把一个 1 变成 -1，neg_count 就成了 3，3 > 4/2，总和又变负了，得不偿失呀！

所以，最稳妥、最划算的方法就是方案一。因此，如果在第一步之后，-1 的数量是奇数，我们就需要再多加一次操作。

总结一下我们的两步走策略：

计算需要把多少个 -1 变成 1 才能使总和非负，记下操作数。
检查经过第一步后，剩余的 -1 数量是否为奇数。如果是，操作数再加 1。

这样就能得到最少的操作次数啦！

题解代码 (C++ Solution)

下面是根据我们的思路写出的 C++ 代码，咱给加上了一些可爱的注释，方便大家理解哦！

cpp

#include <iostream>

// 每个测试用例的处理函数喵~
void solve() {
    int n;
    std::cin >> n;
    
    int neg_count = 0; // 用来数一数有多少个 -1
    for (int i = 0; i < n; ++i) {
        int a;
        std::cin >> a;
        if (a == -1) {
            neg_count++;
        }
    }
    
    int ops = 0; // 记录总操作次数
    
    // 第一步：优先满足“和非负”条件 (Sum >= 0)
    // 这意味着 -1 的数量不能超过 n/2。
    // 如果 -1 太多了，我们就必须把多出来的变成 1，哼哼~
    if (neg_count > n / 2) {
        int flips_needed = neg_count - (n / 2);
        ops += flips_needed;
        neg_count -= flips_needed; // 更新 -1 的数量
    }
    
    // 第二步：在满足和非负的基础上，满足“积为一”条件 (Product = 1)
    // 这意味着 -1 的数量必须是偶数。
    // 如果处理完和之后，-1 的数量是奇数...
    if (neg_count % 2 != 0) {
        // ...那就再来一次操作！把一个 -1 变成 1 是最稳妥的选择。
        // 这会让 -1 的数量变成偶数，同时总和还会增加，不会破坏第一个条件。
        ops++;
    }
    
    std::cout << ops << std::endl;
}

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

题目大意 (Problem Analysis) ​

解题思路 (Solution Approach) ​

题解代码 (C++ Solution) ​

相关知识点 (Knowledge Corner) ​

题目大意 (Problem Analysis)

解题思路 (Solution Approach)

题解代码 (C++ Solution)

相关知识点 (Knowledge Corner)