C++ 高效求解：有序数组与二分查找优化 (P3338)

好的，我们来分析并优化这个问题。 你的初始代码使用了两层循环，时间复杂度是 **O(n²)**。当 n 最大为 10⁵ 时，10⁵ 的平方是 10¹⁰，这个操作量对于 1 秒的时间限制来说太大了，必然导致超时（TLE）。 我们需要找到一个更高效的算法，通常能将复杂度降低到 **O(n log n)** 或 **O(n)**。 ### 🧠 核心优化思路 题目的要求是找到所有满足 `a[i] + b[j] >= 0` 的 (i, j) 对。 等价于：对于数组 a 中的每个元素 `a[i]`，我们需要找到数组 b 中有多少个元素 `b[j]` 满足 `b[j] >= -a[i]`。 由于数组 b 中的元素是**负整数**，我们考虑以下优化策略： 1. **排序数组 b**：对数组 b 进行**升序排序**。排序后，数组 b 中的元素从小到大排列（由于是负数，所以比如 -5, -4, -3, ...）。 2. **使用二分查找**：对于数组 a 中的每个元素 `a[i]`： * 计算目标值 `target = -a[i]`。 * 在排序后的数组 b 中，使用二分查找找到**第一个大于等于 target 的元素的索引** `pos`。 * 那么，从 `pos` 到数组末尾的所有元素 `b[pos]`, `b[pos+1]`, ..., `b[n-1]` 都满足 `b[j] >= target`，也就是 `a[i] + b[j] >= 0`。 * 对于当前的 `a[i]`，满足条件的对数是 `n - pos`。 3. **累加结果**：将每个 `a[i]` 对应的对数累加起来，得到最终答案。 **复杂度分析**： * **时间复杂度**： * 排序数组 b：O(n log n) * 对每个 a[i] 进行二分查找：O(n log n) * 总时间复杂度：**O(n log n)** * **空间复杂度**： * O(1) 或 O(n)，取决于排序算法。通常为 O(log n)。 ### 📝 优化后的 C++ 代码 ```cpp #include <iostream> #include <vector> #include <algorithm> // 用于 sort, lower_bound using namespace std; int main() { int n; cin >> n; vector<int> a(n); vector<int> b(n); // 读取数组 a for (int i = 0; i < n; ++i) { cin >> a[i]; } // 读取数组 b for (int i = 0; i < n; ++i) { cin >> b[i]; } // 1. 对数组 b 进行升序排序 sort(b.begin(), b.end()); long long count = 0; // 使用 long long 防止结果溢出 // 2. 遍历数组 a，对每个 a[i] 在 b 中二分查找 for (int i = 0; i < n; ++i) { int target = -a[i]; // 我们需要 b[j] >= target // 在排序后的 b 中，找到第一个 >= target 的元素位置 // lower_bound 返回指向第一个不小于 target 的元素的迭代器 auto it = lower_bound(b.begin(), b.end(), target); // 计算从 it 到数组末尾的元素个数 // distance 计算迭代器之间的元素个数 count += distance(it, b.end()); } cout << count << endl; return 0; } ``` ### 💡 关键函数说明 * `sort(b.begin(), b.end());`： * 这是 C++ 标准库中的排序函数，默认对指定范围内的元素进行升序排序。复杂度为 O(n log n)。 * `lower_bound(b.begin(), b.end(), target);`： * 这是一个二分查找函数，用于在**已排序**的区间 `[b.begin(), b.end())` 中，查找第一个**不小于**（即大于或等于） `target` 的元素。 * 它返回一个指向该元素的迭代器。如果没有找到，则返回 `b.end()`（即指向最后一个元素之后的位置）。 * `distance(it, b.end())`： * 计算迭代器 `it` 到 `b.end()` 之间的距离，即元素个数。 * 如果 `it` 等于 `b.end()`，则 `distance` 返回 0，表示没有找到满足条件的元素。 * `long long count = 0;`： * 因为 n 最大为 10⁵，在最坏情况下（所有 a[i] 为正且很大，所有 b[j] 为负且很小），总共有 `n * n = 10¹⁰` 个组合，这已经超出了 `int` 类型（约 2.1 × 10⁹）的表示范围。必须使用 `long long` 或更大类型来存储结果。 ### 💎 开发建议 1. **算法先行**：在编写代码前，先分析问题的约束条件（n <= 10⁵），意识到 O(n²) 不可行，然后思考如何利用排序、二分查找、双指针等技巧降低复杂度。 2. **注意数据类型溢出**：在处理大规模乘法或加法结果时，要谨慎选择数据类型，避免溢出。`int` 的范围大约 `[-2.1e9, 2.1e9]`，而 `n*n` 可达 `1e10`，超出此范围。本题中，`long long` （通常 64位，范围 `[-9e18, 9e18]`）可以安全存储。 3. **善用标准库**：C++ 的标准库提供了非常多的高效、健壮的算法和数据结构（如 `sort`、`lower_bound`、`vector`）。熟练掌握这些工具，可以让你在解决问题时事半功倍。 4. **测试边界情况**：测试用例应该包括边界情况，例如 `n=1`、`a` 和 `b` 均为极限值（如最大正数和最小负数）、所有组合均满足条件、以及没有任何组合满足条件的情况。 ######[AI写代码神器 | 1412点数解答 | 2026-06-07 15:21:47]