【CSP试题回顾】202209-2-何以包邮？
CSP-202209-2-何以包邮？
解题关键：计算数组所以子序列和
题目是一个典型的动态规划问题，可以翻译为：给定一个数组
a，该数组包含n个正整数。你需要找出所有可能的子序列的和，并将这些和保存下来。现在，给定一个数x，你需要找出在所有可能的子序列的和中，最小的但是大于或等于x的那个和。如果没有和大于或等于x，则返回-1（题目描述中并未明确提及此情况，但这通常是类似问题的一种处理方式）。这个问题的关键在于如何有效地计算所有可能子序列的和，并快速找到满足条件的最小和。
本题的解法是通过动态编程方法来计算数组的所有子序列和，假设输入数组 a = [1, 3, 2]，我们将逐步说明代码如何计算所有可能子序列的和。初始时，arr = []（空数组），表示还没有计算任何子序列的和。
第一步：处理元素 1
- 将
1加入到arr，arr变为[1]。 - 这时，
arr包含的是数值1和它自身的和（因为单个元素也被视为子序列）。
第二步：处理元素 3
- 遍历当前的
arr（只包含1），并将3添加到每个元素上，得到新的子序列和为4（1 + 3）。然后将新和4加入arr，此时arr = [1, 4]。 - 同时，将
3本身也添加到arr，因为它自己也是一个子序列，此时arr变为[1, 4, 3]。 - 对
arr进行排序和去重（去重是为了节省空间开销，此例中不需要去重），得到[1, 3, 4]。
第三步：处理元素 2
- 遍历当前的
arr（包含[1, 3, 4]），并将2添加到每个元素上，得到新的子序列和3（1 + 2）、5（3 + 2）、6（4 + 2）。将这些新和加入arr，此时arr = [1, 3, 4, 3, 5, 6]。 - 将
2本身也添加到arr，因为它自己也是一个子序列，此时arr变为[1, 3, 4, 3, 5, 6, 2]。 - 再次对
arr进行排序和去重，得到[1, 2, 3, 4, 5, 6]。
现在，arr 包含了数组 [1, 3, 2] 所有可能的子序列和：1（来自子序列 [1]）、2（来自子序列 [2]）、3（来自子序列 [1, 2] 或 [3]）、4（来自子序列 [1, 3]）、5（来自子序列 [2, 3]）、6（来自子序列 [1, 2, 3]）。通过这种方法，代码逐个处理数组中的每个元素，并动态地构建出所有可能的子序列和的集合。
解题思路
上述代码使用了C++ STL中的
set来高效地处理和存储所有可能的子序列和。这里也采用了类似的动态规划思想，但与前一种方法相比，使用set的优点在于自动排序和去重。
1.set介绍
set 是C++标准模板库（STL）中的一个容器，用于存储唯一元素，按照特定顺序排列。set 中的元素默认按升序排列，且所有元素都是唯一的，自动去重。set 的实现通常基于红黑树，一个自平衡的二叉搜索树，这使得其大多数操作（如插入、删除、搜索）的时间复杂度为 O(log n)。
2.解题思路
-
变量初始化
- 定义整数
n和x，其中n是数组的长度，x是我们要查找的目标值。 - 创建一个
set类型的变量sums，并将0插入其中。在动态规划中，0表示空子序列的和，是初始状态。
- 定义整数
-
遍历数组
- 遍历输入的每个元素
t。 - 创建一个新的
setnewSums来存储新增的子序列和。 - 遍历
sums中已存在的每个和，将这个和与新元素t相加，然后将结果添加到newSums中。
- 遍历输入的每个元素
-
更新子序列和的集合
- 将
newSums中的所有元素添加到sums中。由于sums是一个set，这个操作会自动去重并保持元素的排序。
- 将
-
查找和输出
- 使用
sums.lower_bound(x)查找第一个大于或等于x的元素。lower_bound是一个二分查找方法，可以在对数时间内完成，最后输出找到的元素。
- 使用
完整代码
#include <iostream>
#include <set>
using namespace std;int main() {int n, x;cin >> n >> x;set<int> sums;sums.insert(0);for (int i = 0; i < n; i++) {int t;cin >> t;set<int> newSums; // 创建一个新的set来存储新的和 for (auto it : sums) { // 遍历现有的和，添加新的和newSums.insert(it + t);}sums.insert(newSums.begin(), newSums.end()); // 将新的和合并到主set中}auto it = sums.lower_bound(x); // 使用lower_bound查找一个大于或等于x的值，这是一个log(n)的操作cout << *it;return 0;
}
