用C++解决寻找黄金分割点问题：附代码与详细解释

以下是解决该问题的C++代码： ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n; // 读取整数 n，表示数组的长度 cin >> n; vector<int> a(n + 1); // 前缀和数组，用于存储到每个位置的元素总和 vector<int> prefix_sum(n + 1, 0); // 读取数组元素，并计算前缀和 for (int i = 1; i <= n; ++i) { cin >> a[i]; prefix_sum[i] = prefix_sum[i - 1] + a[i]; } // 遍历数组，寻找黄金分隔点 for (int i = 1; i <= n; ++i) { // 计算左侧元素的总和 int left_sum = prefix_sum[i - 1]; // 计算右侧元素的总和 int right_sum = prefix_sum[n] - prefix_sum[i]; // 判断左侧元素总和是否等于右侧元素总和的两倍 if (left_sum == 2 * right_sum) { cout << i << endl; return 0; } } // 如果未找到符合条件的分割点，输出 -1 cout << -1 << endl; return 0; } ``` ### 代码解释： 1. **输入处理**：首先读取整数 `n`，表示数组的长度。然后读取 `n` 个整数，存储在数组 `a` 中。 2. **前缀和计算**：使用 `prefix_sum` 数组来计算从数组开头到每个位置的元素总和。这样可以在 $O(1)$ 的时间复杂度内计算任意区间的元素和。 3. **寻找黄金分隔点**：遍历数组，对于每个位置 `i`，计算其左侧元素的总和 `left_sum` 和右侧元素的总和 `right_sum`。如果 `left_sum` 等于 `right_sum` 的两倍，则 `i` 是黄金分隔点，输出 `i` 并结束程序。 4. **未找到分隔点的处理**：如果遍历完整个数组都没有找到符合条件的分割点，输出 `-1`。 ### 复杂度分析： - **时间复杂度**：$O(n)$，主要是因为需要遍历一次数组来计算前缀和，再遍历一次数组来寻找黄金分隔点。 - **空间复杂度**：$O(n)$，主要是因为需要使用一个长度为 `n` 的前缀和数组。 ######[AI问答 | 595点数解答 | 2026-08-29 20:24:30]