Maximum Product Strikes Back - 题解

比赛与标签

比赛: Codeforces Round 780 (Div. 3) 标签: brute force, implementation, math, two pointers 难度: *1600

题目大意喵~

主人你好呀！这道题是这样的喵~

我们拿到一个只包含 -2, -1, 0, 1, 2 这些数字的数组 a。我们的任务是，可以从数组的开头去掉任意数量的元素（x 个），也可以从数组的末尾去掉任意数量的元素（y 个），剩下的中间部分就是一个新的子数组啦。

我们的目标是让这个新的子数组里所有元素的乘积最大化！最后，我们要告诉裁判，我们从开头去掉了几个元素（x），从结尾去掉了几个元素（y）。如果有很多种方法都能得到最大的乘积，随便哪一种都可以的说。

哦对了，如果最后我们把整个数组都删掉了（也就是一个空数组），它的乘积要算作 1 呐！

解题思路，我的爪子已经开始痒了！

呐呐，要让乘积最大，我们得像小猫抓线团一样，抓住问题的关键点喵~

关键点1：讨厌的 0

数组里有 0 的话，任何包含 0 的子数组乘积都会变成 0！这可太糟糕了，因为我们总能通过选择一个空数组得到乘积 1，这通常比 0 要好。所以，我们最优的子数组肯定不能包含 0 的说。

这给了我们一个超棒的启发：0 就像一堵墙，把整个数组分成了好几个独立的段落。我们只需要在这些不含 0 的段落里分别寻找最优解，然后比较一下哪个段落能产生的乘积最大就好啦！

关键点2：什么决定了乘积的大小？

观察一下数组里的数字：1 和 -1 只会改变符号，不会改变乘积的绝对值。真正能让乘积绝对值变大的是 2 和 -2！所以，我们的核心目标就变成了：在保证乘积为正的前提下，找到一个子数组，让它包含的 2 和 -2 的数量最多。

关键点3：正负号的魔法

一个乘积是正是负，完全取决于负数的个数。

• 偶数个负数相乘，结果是正数。
• 奇数个负数相乘，结果是负数。

我们肯定想要一个正数的乘积，因为它总是比负数大。

综合策略喵！

结合以上几点，我们的完美策略就出炉啦：

1. 分段处理：我们以 0 为分界线，把原数组分成若干个小段。对每个小段单独分析。

2. 分析每个小段：对于一个不含 0 的小段，我们先统计一下它里面负数的总个数 (neg_count) 和 2 或 -2 的总个数 (twos_count)。

   • 情况A：如果 neg_count 是偶数 太棒了！整个小段的乘积就是正数。我们直接取下整个小段，它能贡献的 2 的数量就是 twos_count。这是这个小段能给出的最优解了！

   • 情况B：如果 neg_count 是奇数 呜... 整个小段乘起来是负数，不行不行。为了让它变成正数，我们必须去掉奇数个负数。最简单的办法就是只去掉一个负数。为了保留尽可能多的 2 和 -2，我们有两种选择：

     1. 从段落的开头一直删到第一个负数（包括它）。
     2. 从段落的结尾一直删到最后一个负数（包括它）。

     我们分别计算这两种选择剩下的子数组里有多少个 2 和 -2，然后取那个数量更多的方案作为这个小段的最优解。

3. 全局最优：我们维护一个全局的最大 2 的数量 max_twos，和对应的答案 ans_l, ans_r。初始时，我们可以认为我们删掉了所有元素，得到一个空数组，乘积为 1，此时 max_twos 是 0。然后，我们用每个小段算出的最优解来挑战这个全局最优值。如果某个方案的 twos_count 更大，我们就更新 max_twos 和对应的 ans_l, ans_r。

这样一步步下来，我们就能找到最终的答案啦，喵~

代码实现，看我一顿操作！

#include <iostream>
#include <vector>
#include <cmath>

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // max_twos 记录目前找到的最优子数组中 2 和 -2 的数量。
    // 乘积的绝对值就是 2^max_twos，所以最大化 max_twos 就是最大化乘积。
    int max_twos = 0;
    // ans_l 和 ans_r 记录要从左边和右边移除的元素数量。
    // 默认是移除所有元素，得到一个空数组，乘积为 1。
    int ans_l = n, ans_r = 0;

    int current_start = 0;
    // 我们遍历数组，用 0 来作为分界点处理各个段落。
    // 循环到 n 是为了能正确处理最后一个段落。
    for (int i = 0; i <= n; ++i) {
        // 当遇到 0 或者遍历到数组末尾时，处理 a[current_start ... i-1] 这个段落
        if (i == n || a[i] == 0) {
            if (current_start < i) { // 确保这是一个非空段落
                int twos = 0;
                int neg_count = 0;
                int first_neg = -1, last_neg = -1;

                // 统计这个段落的信息
                for (int j = current_start; j < i; ++j) {
                    if (std::abs(a[j]) == 2) {
                        twos++;
                    }
                    if (a[j] < 0) {
                        neg_count++;
                        if (first_neg == -1) {
                            first_neg = j;
                        }
                        last_neg = j;
                    }
                }

                if (neg_count % 2 == 0) {
                    // 如果负数个数是偶数，整个段落的乘积是正的。
                    // 我们可以取下整个段落。
                    if (twos > max_twos) {
                        max_twos = twos;
                        ans_l = current_start;
                        ans_r = n - i;
                    }
                } else {
                    // 如果负数个数是奇数，我们需要移除一部分来使乘积为正。
                    
                    // 方案1: 移除从开头到第一个负数的部分
                    int twos_after_first = 0;
                    for (int j = first_neg + 1; j < i; ++j) {
                        if (std::abs(a[j]) == 2) {
                            twos_after_first++;
                        }
                    }
                    if (twos_after_first > max_twos) {
                        max_twos = twos_after_first;
                        ans_l = first_neg + 1;
                        ans_r = n - i;
                    }

                    // 方案2: 移除从最后一个负数到结尾的部分
                    int twos_before_last = 0;
                    for (int j = current_start; j < last_neg; ++j) {
                        if (std::abs(a[j]) == 2) {
                            twos_before_last++;
                        }
                    }
                    if (twos_before_last > max_twos) {
                        max_twos = twos_before_last;
                        ans_l = current_start;
                        ans_r = n - last_neg;
                    }
                }
            }
            // 移动到下一个段落的起始点
            current_start = i + 1;
        }
    }

    std::cout << ans_l << " " << ans_r << "\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(n) 的说 我们只用一个循环从头到尾扫描了整个数组。虽然里面还有一些小循环，但每个元素最多只会被访问常数次（在统计段落信息时）。所以总的时间复杂度是线性的，也就是 O(n)，非常高效喵！

• 空间复杂度: O(n) 的说 我们主要的空间开销是用来存储输入的数组 a。除此之外，只用了一些常量级别的变量。所以空间复杂度是 O(n) 呐。

知识点与总结，快拿小本本记下来！

这道题真有趣，让我们学到了不少东西呢！

1. 分治思想（被0分割）: 遇到像 0 这样有特殊性质的元素，可以考虑用它来分割问题，把一个大问题变成几个小问题。这是算法设计中非常重要的思想！
2. 贪心与分类讨论: 我们的核心策略是贪心地最大化 2 和 -2 的数量。为了实现这个目标，我们根据负数个数的奇偶性进行了分类讨论，每种情况都采取了最优的局部策略。
3. 注意边界和初始值: 别忘了空数组乘积为 1 这个重要的初始条件！它为我们的比较提供了一个基准。代码中通过初始化 max_twos = 0 和 ans_l = n, ans_r = 0 巧妙地处理了这一点。

希望我的题解对你有帮助喵！多做题，多思考，你也能成为算法大师的！加油，喵~