G1. Subsequence Addition (Easy Version) - 题解

比赛与标签

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

题目大意喵~

主人 sama，你好呀！这道题是说，我们一开始有一个只包含数字 1 的数组 a，喵~ 我们可以进行一种神奇的操作：选择 a 里的任意一些数字（这叫作子序列），把它们的和加到 a 数组里。

现在，题目会给我们一个最终的目标数组 c，问我们能不能通过若干次（也可能是零次）这种操作，把初始的 a = [1] 变成一个包含了 c 中所有元素的数组呢？

需要注意的是，新加进去的数字可以放在数组的任何位置，所以最终数组元素的顺序是不重要的，只要元素和数量跟 c 一样就可以了呐。

解题思路呐！

嘿嘿，这个问题看起来有点复杂，但只要我们抓住关键点，它就会变得像猫咪的毛线球一样好解开啦！

第一步：排序大法好！

题目说最终得到的数组 a 只要包含 c 的所有元素就行，顺序不重要。这可是一个非常重要的提示喵！当我们不关心顺序时，最好的办法就是 先把目标数组 c 排个序！这样一来，我们就只需要考虑如何按从小到大的顺序，一个一个地“创造”出 c 中的每个元素了，思路会清晰很多的说。

第二步：万物之始，必须是 `1`！

我们最开始的数组是 a = [1]。之后所有新生成的数字，都来自于对 a 中已有元素的求和。这意味着，我们能创造的最小新数字也是 1（选择子序列 [1]）。所以，如果我们想得到目标数组 c，那么 c 里面必须得有一个 1 才行呀！

排完序之后，如果 c[0]（也就是 c 中最小的元素）都不是 1，那我们连第一步都迈不出去，肯定无法完成任务。所以，如果 c[0] != 1，直接输出 "NO" 就好啦，喵~

第三步：贪心的力量！

好！现在我们已经有了一个排好序的、并且以 1 开头的数组 c。接下来该怎么判断呢？我们可以用贪心的思想来模拟这个过程。

我们维护一个变量 current_sum，表示当前我们已经成功“创造”并拥有的所有数字的总和。

初始状态：我们已经确认了 c[0] 是 1，这是我们与生俱来的（或者说，是题目给的初始条件）。所以，我们拥有的数字是 {1}，那么 current_sum 的初始值就是 1。
递推过程：我们从 c 的第二个元素 c[1] 开始，依次检查到 c[n-1]。对于当前的元素 c[i]，我们要判断是否能用我们 已经拥有的 数字（也就是 c[0], c[1], ..., c[i-1]）通过求和得到它。
想一想，用我们已有的数字，能凑出来的最大和是多少呢？当然是把它们全都加起来啦！这个和正好就是我们维护的 current_sum！
所以，对于 c[i]，如果它比 current_sum 还要大，那我们无论如何也凑不出 c[i] 了，对吧？因为我们能凑出的最大值就是 current_sum。这时，就说明无法构造出目标数组 c，应该输出 "NO"。
那如果 c[i] <= current_sum 呢？是不是就一定能凑出来？是的喵！这里有一个很棒的数学性质：如果一个正整数集合 {s_1, s_2, ...} 满足 s_1=1，并且对于后面的每一个数 s_k，都有 s_k <= s_1 + ... + s_{k-1}，那么这个集合的子集和可以表示出 1 到 s_1 + ... + s_k 之间的任何一个整数！
在我们的问题里，这个性质保证了只要 c[i] <= current_sum，我们就一定能从 c[0] 到 c[i-1] 中选出一个子序列，它们的和恰好等于 c[i]。
更新状态：如果 c[i] 的检查通过了（即 c[i] <= current_sum），说明我们成功“创造”了 c[i]。现在，我们的工具箱里又多了一个数字 c[i]，所以我们要更新 current_sum，把它加上 c[i]。

如果我们能顺利地检查完 c 中的所有元素，都没有出现 c[i] > current_sum 的情况，那就说明这个目标数组 c 是可以被构造出来的！输出 "YES"！

总结一下这个可爱的贪心策略：

对 c 排序。
检查 c[0] 是否为 1。
初始化 prefix_sum = 1。
从 i=1 开始遍历 c，如果 c[i] > prefix_sum，则失败。否则，prefix_sum += c[i]。
如果遍历完成，则成功。

代码实现喵~

cpp

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

using namespace std;

int main() {
    // 加速输入输出，让程序跑得像猫一样快，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> c(n);
        for (int i = 0; i < n; i++) {
            cin >> c[i];
        }

        // 核心第一步：排序！这样我们就可以从小到大处理了
        sort(c.begin(), c.end());

        // 检查最基本的情况：最小的元素必须是 1
        if (c[0] != 1) {
            cout << "NO\n";
            continue; // 处理下一个测试用例
        }

        // 用 long long 防止前缀和溢出，是个好习惯哦
        long long prefix_sum = 1;
        bool valid = true; // 一个标记，记录是否一直合法

        // 从第二个元素开始，进行贪心检查
        for (int i = 1; i < n; i++) {
            // 这就是我们的贪心核心判断！
            // 如果当前要构造的数 c[i] 比我们能凑出的最大和 prefix_sum 还大
            // 那就肯定没希望了呀
            if (c[i] > prefix_sum) {
                valid = false;
                break; // 直接中断循环
            }
            // 如果可以构造，就把 c[i] 加入我们的“工具箱”
            // 更新前缀和，让它能用来构造更大的数
            prefix_sum += c[i];
        }

        cout << (valid ? "YES\n" : "NO\n");
    }
    return 0;
}

复杂度分析的说

时间复杂度: O(N log N) 的说。主要是因为 sort(c.begin(), c.end()) 这一步，它的时间复杂度是 O(N log N)。后面的循环只遍历一次数组，是 O(N) 的。所以总的时间复杂度由排序决定，就是 O(N log N) 啦。
空间复杂度: O(N) 的说。我们用了一个 vector<int> c 来存储输入的 n 个整数，所以空间复杂度是 O(N)。如果算上输入本身，就是这个值；如果不算，那额外空间是 O(1) 的。

知识点与总结nya~

这道题虽然标签很多，但核心思想是贪心和排序，是一个非常经典的组合拳呢！

排序的重要性：当题目中的操作和顺序无关时，首先要想到排序！排序能把一个混乱的问题变得有序，为贪心、动态规划等算法铺平道路。
贪心选择性质：本题的贪心选择是“每次都尝试构造当前最小的、还未构造的数”。我们证明了这个选择的正确性：只要 c[i] 不大于之前所有数的和，它就一定能被构造出来。
前缀和思想：我们用 prefix_sum 变量来实时维护当前可用数字的总和，这其实就是前缀和的思想。它让我们能以 O(1) 的时间复杂度进行关键的判断。
注意边界条件：c[0] != 1 是一个很容易被发现但必须处理的边界。还有，虽然这题数据范围小，但在计算累加和时，养成使用 long long 的好习惯可以避免很多不必要的错误哦！

希望这篇题解能帮助到主人 sama！解题就像逗猫棒，找到窍门就乐趣无穷啦！继续加油喵~ ✨

G1. Subsequence Addition (Easy Version) - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路呐！ ​

第一步：排序大法好！ ​

第二步：万物之始，必须是 1！ ​

第三步：贪心的力量！ ​

代码实现喵~ ​

复杂度分析的说 ​

知识点与总结nya~ ​