Moe's CF Life

喵哈喽~ 主人！今天由我，你最可爱的小猫娘，来为你讲解一道关于数组分割的有趣问题哦！这道题目就像是给一堆毛线球分类，只要找到正确的规律，就能轻松解决啦，喵~

题目大意

这道题是说，有一个叫 Vitaly 的人，他有一个包含 n 个不同整数的数组。他想把这个数组分成三个非空的集合，并且需要满足下面三个条件哦：

第一个集合里所有数字的乘积必须是负数 (< 0)。
第二个集合里所有数字的乘积必须是正数 (> 0)。
第三个集合里所有数字的乘积必须是零 (= 0)。

数组里的每个数字都必须恰好属于这三个集合中的一个。题目保证一定有解，所以我们不用担心分不出来的情况啦！

解题思路

这个问题看起来有点绕，但其实只要我们像小猫咪一样，把问题分解成一小步一小步，就会发现它很简单哦！关键在于数字的正负性和零的特殊性质。

首先，我们先把数组里的所有数字分成三类：负数、正数和零。这样做能让我们的思路清晰很多呢。

接下来，我们来一个一个地构造这三个集合：

集合三：乘积为 0

这是最容易满足的条件啦！要想让乘积为 0，集合里只需要有一个 0 就可以了，对吧？既然题目保证有解，那么输入的数组里一定至少有一个 0。所以，我们把输入数组里所有的 0 都放进第三个集合。这样，集合三的要求就稳稳地满足了！

集合一：乘积为负

怎么样才能让乘积是负数呢？最简单的方法就是，这个集合里只放一个负数！同样，因为题目保证有解，所以输入的数组里一定至少有一个负数。我们就从负数堆里随便拿一个，放进第一个集合。搞定，喵！

集合二：乘积为正

这个稍微需要动动脑筋啦。要让乘积为正，有两种主要情况：

集合里全是正数：如果我们的输入里有正数，那就太棒了！我们把所有的正数都放进第二个集合，它们的乘积肯定是正数。
集合里有两个负数：欸？要是输入里一个正数都没有怎么办呀？别担心，负负得正嘛！既然题目保证有解，那么当没有正数时，负数的数量肯定足够我们分配。我们已经给第一个集合分配了一个负数了，我们再从剩下的负数里拿出两个，放进第二个集合。-2 * -3 = 6，你看，乘积不就变成正数了嘛！

处理剩下的数字

好啦，现在三个集合的核心成员都确定了，但可能还有一些数字（肯定是剩下的负数）没有被分配。这些“无家可归”的小可怜该放到哪里去呢？

不能放进集合一：如果再放一个负数进去，乘积就可能从负数变成正数了。
不能放进集合二：如果再放一个负数进去，乘积就可能从正数变成负数了。
只能放进集合三！为什么呢？因为集合三里已经有 0 了呀！任何数乘以 0 的结果都是 0。所以，我们把所有剩下的数字都扔进集合三，完全不会影响它的乘积（永远是 0），而且还满足了“每个数字都必须被分配”的要求。完美！

总结一下我们的策略就是：

先将所有数分为负数、正数、零三个列表。
集合一：取一个负数。
集合二：如果正数列表不为空，则集合二就是所有正数；如果正数列表为空，则从负数列表中再取两个数。
集合三：放入所有的零，以及所有分配完后剩下的数。

这样一来，我们就能百分百构造出一个符合题意的解啦！

题解

下面是具体的 C++ 代码实现，我已经加上了可爱的注释哦，喵~

cpp

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

// 一个用来打印集合的小助手函数，喵~
void print_set(const std::vector<int>& s) {
    std::cout << s.size();
    for (int x : s) {
        std::cout << " " << x;
    }
    std::cout << "\n";
}

int main() {
    // 让输入输出变得像猫咪一样快的小魔法！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    // 先把数字们按正、负、零分好类，喵~
    std::vector<int> neg, pos, zero;
    for (int i = 0; i < n; ++i) {
        int val;
        std::cin >> val;
        if (val < 0) {
            neg.push_back(val);
        } else if (val > 0) {
            pos.push_back(val);
        } else {
            zero.push_back(val);
        }
    }

    // 这就是我们要构造的三个集合啦
    std::vector<int> set1, set2, set3;

    // --- 构造集合一：乘积 < 0 ---
    // 只需要一个负数就够啦。题目保证肯定有负数，所以我们大胆地拿走一个！
    set1.push_back(neg.back());
    neg.pop_back();

    // --- 构造集合二：乘积 > 0 ---
    // 如果有正数，就全给集合二
    if (!pos.empty()) {
        set2 = pos;
    } else {
        // 如果没有正数，那就拿两个负数来凑一个正数乘积
        // 题目保证在这种情况下，负数数量肯定 >= 3
        set2.push_back(neg.back());
        neg.pop_back();
        set2.push_back(neg.back());
        neg.pop_back();
    }

    // --- 构造集合三：乘积 = 0 ---
    // 这个集合必须包含所有的零
    set3 = zero;
    // 剩下的所有数字（只可能是负数了）都丢给集合三
    // 因为和0相乘还是0，不会影响结果~
    set3.insert(set3.end(), neg.begin(), neg.end());

    // 按格式打印三个集合
    print_set(set1);
    print_set(set2);
    print_set(set3);

    return 0;
}

知识点介绍

这道题虽然简单，但也涉及了一些有用的基础知识呢！

乘法基本性质：这是解题的核心！
- 负数 × 负数 = 正数
- 奇数个负数相乘 = 负数
- 偶数个负数相乘 = 正数
- 任何数 × 0 = 0 理解这些，就能明白我们为什么可以那样构造集合啦。
构造性算法 (Constructive Algorithm) 这道题是一个典型的构造性问题。我们不需要去搜索所有可能的分法，而是根据题目给出的性质和约束，直接一步步地“构造”出一个符合要求的解。在算法竞赛中，这类问题很常见哦！
C++ std::vectorvector 是 C++ 中一个非常好用的动态数组容器。
- push_back()：在末尾添加一个元素，就像猫咪把玩具叼到篮子里。
- pop_back()：移除末尾的元素。
- insert()：可以在任意位置插入元素。代码中用它把一个 vector 的所有元素高效地追加到另一个 vector 的末尾。
- .size() 和 .empty()：分别用于获取大小和判断是否为空，非常方便。

好啦，这次的题解就到这里啦！主人有没有觉得豁然开朗呢？下次遇到类似的问题，也要像小猫一样，敏锐地抓住问题的关键点哦！喵~

题目大意 ​

解题思路 ​

集合三：乘积为 0 ​

集合一：乘积为负 ​

集合二：乘积为正 ​

处理剩下的数字 ​

题解 ​

知识点介绍 ​