G2. Subsequence Addition (Hard Version) - 题解

比赛与标签

比赛: Codeforces Round 859 (Div. 4) 标签: bitmasks, dp, greedy, implementation, sortings 难度: *1100

题目大意喵~？

这道题是说，我们一开始有一个只包含数字 1 的数组 a，也就是 a = [1]。我们可以进行一种操作：从数组 a 中选择任意一些数字（这叫作子序列），把它们的和算出来，然后把这个和作为一个新元素加回到数组 a 的任何位置。

现在，题目会给我们一个最终的目标数组 c，问我们是否能通过任意多次这样的操作，从最初的 [1] 变成目标数组 c 呢？

举个栗子，如果目标是 c = [1, 2, 1]，我们可以这样做：

初始 a = [1]。
选择子序列 [1]，和是 1。把 1 加进去，a 变成 [1, 1]。
选择子序列 [1, 1]，和是 2。把 2 加进去，a 变成 [1, 2, 1]。成功啦！

要注意的是，最终数组 c 里的元素顺序不重要，只要我们能凑齐这些数字就行了哦！

贪心大法好喵！

这道题的核心在于，我们每次添加的新数字，都是由已有的数字相加得来的。这给了我们一个很重要的启示：新生成的数字总是比构成它的任何一个数字都要大（除非子序列只有一个元素，但我们只关心能生成哪些新数）。

既然我们是“从小到大”地生成数字，一个非常自然的想法就是——排序！喵~！

让我们先把目标数组 c 从小到大排个序。这样我们就可以按顺序来考虑如何生成每一个元素了。

第一个元素必须是 1：我们最初只有 1，所有后续生成的数字都是正整数的和，所以也都是正数。这意味着我们能生成的最小数字就是 1。如果排序后的 c 数组第一个元素 c[0] 都不是 1，那我们连起点都造不出来，肯定是不可能完成的，直接说 "NO" 就好啦！
贪心构造：好，如果 c[0] 是 1，那我们就有了第一个数字。现在我们来考虑如何生成后面的数字。我们用一个变量 current_sum 来记录当前我们已经拥有的所有数字的总和。
- 一开始，我们有 1，所以 current_sum = 1。
- 现在我们要生成排序后的 c[1]。我们可以用哪些数字来凑呢？当然是已经拥有的数字，也就是 c[0]（即 1）。我们能凑出的最大值就是 current_sum。
- 所以，如果 c[1] 比 current_sum 还大，那我们就绝对凑不出 c[1] 了，对吧？比如我们只有 1，current_sum 是 1，但目标 c[1] 是 3，这是不可能的。所以，一旦发现 c[i] > current_sum，就说明失败了，输出 "NO"。
- 那如果 c[i] <= current_sum 呢？这里有一个非常神奇的性质哦：只要我们拥有的数字集合是从 1 开始，并且每个新数字都不大于之前所有数字的总和，那么我们就能凑出 1 到 current_sum 之间的任何一个整数！是不是很酷？所以，只要 c[i] <= current_sum，我们就一定能凑出 c[i]。
- 一旦我们成功“生成”了 c[i]，它就加入了我们的大家庭！我们把它也加到总和里，更新 current_sum += c[i]，然后继续去挑战下一个数字 c[i+1]。
总结一下策略：
- 对数组 c 排序。
- 检查 c[0] 是否为 1。不是就 "NO"。
- 初始化 current_sum = 1。
- 从 i = 1 开始遍历 c：
  - 如果 c[i] > current_sum，说明无法生成 c[i]，输出 "NO" 并结束。
  - 否则，说明可以生成 c[i]，将它加入我们的集合，更新 current_sum += c[i]。
- 如果循环顺利结束，说明所有数字都能按顺序生成，太棒啦！输出 "YES"！

这个贪心的思路是不是很清晰呢？喵~

代码实现喵~

cpp

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

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

    // 最终数组 c 中元素的顺序不重要，因为新生成的元素可以插入到任何位置。
    // 我们只需要能够凑齐 c 中的所有数字（作为一个多重集）即可。
    // 对 c 进行排序，可以让我们以一个方便的、非递减的顺序来处理元素，这是贪心策略的基础，喵~
    std::sort(c.begin(), c.end());

    // 初始数组 a 是 [1]。所有其他数字都必须由数组中的元素相加得到。
    // 因为所有元素都是正数，任何和都至少是 1。
    // 这意味着目标数组 c 中最小的元素必须是 1。如果不是，就不可能得到 c。
    if (c[0] != 1) {
        std::cout << "NO\n";
        return;
    }

    // 我们使用贪心策略。我们尝试按非递减的顺序生成 c 的元素。
    // `current_sum` 记录了我们到目前为止已经“接受”到我们数组中的所有元素的总和。
    // 最初，我们只有 `1`。
    long long current_sum = 1;

    // 我们从已排序数组 c 的第二个元素开始迭代。
    for (int i = 1; i < n; ++i) {
        // 为了生成元素 c[i]，我们可以使用我们已经生成（并接受）的元素的子序列。
        // 这些元素是 {c[0], c[1], ..., c[i-1]}。
        // 从这些元素中可以形成的最大可能和是它们的总和，也就是 `current_sum`。
        // 如果 c[i] 大于 `current_sum`，那么就不可能生成 c[i] 了，喵呜...
        if (c[i] > current_sum) {
            std::cout << "NO\n";
            return;
        }

        // 如果 c[i] <= current_sum，那么总是可以凑出 c[i] 的！
        // 这是一个已知的性质：如果我们有一个数字集合 {a_1, ..., a_k}，
        // 其中 a_1=1，并且每个后续数字 a_j 不超过其前面所有数字的和，
        // 那么我们就可以凑出高达该集合总和的任何整数。
        // 我们的构造过程在每一步都保证了这个性质成立。
        // 因此，我们可以生成 c[i]。我们通过更新 `current_sum` 将其添加到可用数字集中。
        current_sum += c[i];
    }

    // 如果我们能成功处理 c 中的所有元素，说明这是可能的！
    std::cout << "YES\n";
}

int main() {
    // 为了性能，使用快速 I/O，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析的说

时间复杂度: O(N log N) 的说。最耗时的操作是给数组 c 排序，它的时间复杂度是 O(N log N)。之后我们只需要遍历一次数组，这是 O(N) 的操作。所以总的时间复杂度由排序决定，就是 O(N log N) 啦！
空间复杂度: O(N) 的说。我们主要需要空间来存储输入的数组 c，所以空间复杂度是 O(N)。非常节省空间呢！

知识点与总结喵！

这道题真是一道非常经典的贪心问题，让我们来总结一下学到了什么吧！

贪心算法 (Greedy Algorithm): 核心思想就是做出当前看起来最好的选择。在这里，“最好”的选择就是按从小到大的顺序，检查每个数是否能被前面已有的数凑出来。这个局部最优策略最终导向了全局最优解。
排序的重要性: 很多时候，当我们对问题没有头绪时，对输入数据进行排序往往能揭示出问题的内在结构，让问题变得清晰。对于这道题，排序是应用贪心策略的前提。
一个重要的数学性质: 如果一个正整数集合以 1 开头，并且其中每个元素（从第二个开始）都不大于它前面所有元素的和，那么这个集合可以凑出从 1 到其总和之间的任何整数。这个性质是本题贪心策略正确性的根本保证！

希望这次的题解对你有帮助哦！只要我们开动脑筋，找到问题的关键，再难的题目也会变得像毛线球一样好玩！继续加油，向着更高的目标前进吧，喵~！✨

G2. Subsequence Addition (Hard Version) - 题解 ​

比赛与标签 ​

题目大意喵~？ ​

贪心大法好喵！ ​

代码实现喵~ ​

复杂度分析的说 ​

知识点与总结喵！ ​