PAT乙级C语言1049

### 关于 PAT 乙级 C语言 题目1049 的解题思路与示例代码 #### 解题背景 PAT (Programming Ability Test) 是一项针对编程能力的测试，其乙级考试主要面向初学者和中级程序员。题目通常涉及基础算法、数据结构以及逻辑推理等内容。 对于题目 **1049 数列的片段和**[^4]，以下是详细的解析： --- #### 题目描述 给定一个长度为 \(N\) 的序列 \(A_1, A_2, \ldots, A_N\)，定义该序列的一个片段为连续的一段子序列 \(A_i, A_{i+1}, \ldots, A_j\) （\(1 \leq i \leq j \leq N\)），并将其所有元素之和称为该片段的总和。现在需要计算所有可能片段的总和，并按照升序排列输出这些不同的总和。 --- #### 输入格式 - 第一行包含两个正整数 \(N\) 和 \(M\) (\(1 \leq N \leq 10^5\), \(1 \leq M \leq 10^{18}\))。 - 第二行包含 \(N\) 个整数表示序列中的元素，每个元素范围为 \([-10^9, 10^9]\)。 --- #### 输出格式 - 按照从小到大的顺序输出所有不同片段的总和，每行一个数值。 --- #### 思路分析 由于直接枚举所有的片段会带来极高的时间复杂度（约为 \(O(N^2)\)），因此需要优化解决方案。可以采用前缀和的思想来降低复杂度至 \(O(N \log N)\)，具体如下： 1. 计算数组的前缀和 `prefix_sum`，即 `prefix_sum[i] = sum(A[0..i])`。 2. 对于任意一段区间 `[l, r]`，其片段和可以通过公式 `sum(l, r) = prefix_sum[r] - prefix_sum[l-1]` 得到。 3. 使用集合存储所有可能的不同片段和，最后对集合内的元素进行排序即可。 为了进一步提高效率，在遍历过程中动态维护当前最小值以减少不必要的比较操作。 --- #### 示例代码 以下是一个基于上述思路实现的 C++ 示例代码： ```cpp #include <iostream> #include <vector> #include <set> using namespace std; int main() { int N; long long M; cin >> N >> M; // 输入 N 和 M vector<long long> nums(N); for (auto &num : nums) cin >> num; // 输入序列 set<long long> sums_set; // 存储所有不同的片段和 long long current_sum = 0; // 前缀和加滑动窗口方法 for (int i = 0; i < N; ++i) { current_sum += nums[i]; sums_set.insert(current_sum); // 插入当前前缀和 // 动态更新最小前缀和 static long long min_prefix = 0; if (i > 0 && current_sum >= M + min_prefix) { // 如果满足条件则记录差值 sums_set.insert(current_sum - min_prefix); } min_prefix = min(min_prefix, current_sum); // 更新最小前缀和 } // 将结果存入向量以便排序 vector<long long> result(sums_set.begin(), sums_set.end()); sort(result.begin(), result.end()); // 排序 // 输出结果 for (const auto& val : result) cout << val << endl; return 0; } ``` --- #### 复杂度分析 - 时间复杂度：构建前缀和的时间复杂度为 \(O(N)\)，而插入集合的操作平均时间为 \(O(\log S)\)，其中 \(S\) 是最终集合大小。总体复杂度接近 \(O(N \log N)\)。 - 空间复杂度：额外空间主要用于存储前缀和及去重后的片段和，最坏情况下为 \(O(N)\)。 --- #### 注意事项 - 数据规模较大时需注意变量类型的选取，建议使用 `long long` 类型防止溢出。 - 若输入中有负数，则可能出现多个相同的片段和，应通过集合自动过滤掉重复项。 ---