Moe's CF Life

Myaa~ 主人好呀！今天由我，你们最可爱的小猫娘，来带大家解决一道来自 Codeforces 的题目，叫做 "United We Stand" 喵！这道题看起来有点绕，但只要找到诀窍，就会变得非常简单哦~ 让我们一起来看看吧！

题目大意

题目会给我们一个整数数组 a，我们需要把 a 里的所有数字，分到两个新的、一开始都是空的数组 b 和 c 里面去。

分配的时候要遵守两个规则喵：

数组 b 和 c 都不能是空的。
对于 b 里的任何一个数 b_i 和 c 里的任何一个数 c_j，c_j 都不能整除 b_i。也就是说 b_i % c_j != 0 必须总是成立。

如果能找到这样的分法，就输出分组后的 b 和 c 数组；如果找不到，就输出 -1 呢。

题解方法

喵~ 咱们来分析一下这个核心条件：c 里的任何数都不能整除 b 里的任何数。

要怎么才能保证 c_j 绝对不会整除 b_i 呢？我们可以想一个最最简单的情况。如果一个正整数 x 比另一个正整数 y 要大，那 x 是不是肯定不能整除 y 呀？比如说，5 肯定不能整除 3 嘛。对啦！这就是我们的突破口喵！

所以，一个绝妙的构造方法就出现啦：我们只要让数组 c 里的所有数，都比数组 b 里的所有数大，问题不就解决了吗？

那么，具体要怎么操作呢？

排序：先把输入的数组 a 从小到大排个序。这样最大、最小的元素就一目了然啦。
构造：
- 把数组 a 中最大的那个数（可能有一个或多个）全都放进数组 c。
- 把数组 a 中剩下的所有数全都放进数组 b。
验证：
- 这样一来，b 里的每个数都严格小于 c 里的每个数。根据我们刚才发现的性质，c 里的数就绝对不可能整除 b 里的数了。
- 那 b 和 c 会不会是空的呢？我们来考虑一种特殊情况。

特殊情况：无解

喵呜，如果数组 a 里的所有数字都一模一样，比如 [2, 2, 2]。那不管怎么分，b 和 c 里面都会有 2。这样 c 里的 2 就会整除 b 里的 2，就不满足条件了呀。所以，当所有数字都相同时，是无解的，我们直接输出 -1 就好啦。

一般情况：有解

只要数组 a 里面有不同的数字，那排序之后，最大值和最小值就一定不相等。

我们把最大值放进 c，所以 c 肯定非空。
因为存在比最大值小的数，所以 b 也肯定非空。

两个条件都满足，这个构造方法总是能找到一个解！是不是很聪明喵？

总结一下我们的算法步骤：

读入数组 a。
将 a 排序。
检查排序后的 a 的第一个元素和最后一个元素是否相等。
- 如果相等，说明所有元素都一样，输出 -1。
- 如果不相等，说明有解。找到第一个等于最大值的元素的位置，把它前面的所有元素分给 b，从它开始到结尾的所有元素（也就是所有的最大值）分给 c。然后输出结果。

就这么简单喵~

题解

这是C++的实现代码，我已经加上了可爱的注释哦~

cpp

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

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

    // 先把数组 a 从小到大排个序，这样处理起来最方便了喵
    std::sort(a.begin(), a.end());

    // 如果排序后第一个和最后一个元素都一样，说明所有元素都相同
    // 这种情况是无解的，喵呜~
    if (a[0] == a[n - 1]) {
        std::cout << -1 << "\n";
        return;
    }

    // 否则，一定有解！我们用最简单的构造方法：
    // 把所有不等于最大值的数放进 b，把所有最大值放进 c
    // 这样 c 里的数永远比 b 里的数大，就绝对不会整除了喵！
    
    // 找到最大值
    int max_val = a[n - 1];
    int split_idx = 0;
    // 找到第一个最大值出现的位置
    while (split_idx < n && a[split_idx] != max_val) {
        split_idx++;
    }

    // split_idx 就是数组 b 的长度
    int lb = split_idx;
    // n - split_idx 就是数组 c 的长度
    int lc = n - split_idx;

    std::cout << lb << " " << lc << "\n";

    // 输出数组 b 的所有元素
    for (int i = 0; i < lb; ++i) {
        std::cout << a[i] << (i == lb - 1 ? "" : " ");
    }
    std::cout << "\n";

    // 输出数组 c 的所有元素
    for (int i = 0; i < lc; ++i) {
        std::cout << a[split_idx + i] << (i == lc - 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;
}

知识点介绍

这道题虽然简单，但背后有一些很有用的思想哦！

构造法 (Constructive Algorithms) 这次解题的核心思想就是构造法。我们不是去暴力搜索所有可能的分法，而是直接根据题目的性质，构造出了一个必定满足条件的解。这在算法竞赛里是一种非常强大又优雅的思路呢！当题目要求你找到“一个”满足条件的解时，不妨想一想能不能直接构造一个出来。
排序 (Sorting) 排序是解决很多问题的预处理步骤。你看，我们一排序，最大值、最小值、相同元素都一目了然了，问题瞬间清晰了很多。所以主人要熟练掌握各种排序算法呀喵~
整除性质 (Divisibility Properties) 这里用到了一个超级基础的数论知识：如果正整数 x 能整除正整数 y，那么一定有 x <= y。我们利用了它的逆否命题：如果 y < x，那么 x 肯定不能整除 y。利用这种基础的数学性质，常常能让复杂的问题变得非常简单，数学也很有趣的，对吧喵？

好啦，这道题的讲解就到这里啦！是不是感觉豁然开朗了呢？只要抓住问题的关键性质，再复杂的题目也能被我们轻松解决掉！希望主人喜欢这次的讲解，我们下次再见喵~ 挥爪~

题目大意 ​

题解方法 ​

题解 ​

知识点介绍 ​

题目大意

题解方法

题解

知识点介绍