本题是LeetCode 724 题改写为了标准的 NOI/CSP 普及组风格题目，重点考察前缀和思想的灵活运用。

[OI 基础训练] 寻找平衡点 (前缀和应用)

一、 题目背景与知识点讲解

在上一题“静态数组区间求和”中，我们学习了前缀和的基本定义。本题是前缀和思想的一个经典变体应用。

场景描述： 我们需要在一个序列中找到一个“平衡点”，使得这个点左边所有数字之和等于右边所有数字之和。

1. 暴力解法 (Brute Force) 最朴素的想法是遍历数组中的每一个位置 $i$ 作为候选点。对于每一个 $i$，分别写两个循环计算它左边的和与右边的和，然后比较。

• 复杂度：外层循环 $N$ 次，内层求和 $N$ 次。总复杂度 $O(N^2)$。
• 后果：当 $N=10^5$ 时，运算量过大，会超时。

2. 优化解法：前缀和与数学推导 我们可以利用前缀和（或累加和）的性质将复杂度降为 $O(N)$。

• 核心等式： 设数组所有元素的总和为 $TotalSum$。 当我们在位置 $i$ 时，设该位置左侧（不包含 $A[i]$）的元素之和为 $LeftSum$。 那么，该位置右侧（不包含 $A[i]$）的元素之和可以表示为：

  $$RightSum = TotalSum - LeftSum - A[i]$$

• 平衡条件： 题目要求左侧和等于右侧和，即 $LeftSum == RightSum$。 代入上面的公式：

  $$LeftSum = TotalSum - LeftSum - A[i]$$

  移项整理得：

  $$2 \times LeftSum + A[i] = TotalSum$$

• 算法流程：

  1. 先遍历一遍数组，计算出 $TotalSum$。
  2. 再次遍历数组，维护一个变量 $currentLeftSum$（初始为0）。
  3. 对于每个位置，检查 $2 \times currentLeftSum + A[i] == TotalSum$ 是否成立。
  4. 如果成立，当前位置就是答案。
  5. 如果不成立，将 $A[i]$ 累加到 $currentLeftSum$ 中，继续检查下一个位置。

二、 题目描述

给定一个长度为 $N$ 的整数序列 $A$。请你找到一个中心下标 $P$。 中心下标的定义是：数组中在下标 $P$ 左侧的所有元素之和，等于下标 $P$ 右侧的所有元素之和。

• 如果中心下标位于数组最左端（第 $1$ 个位置），则左侧数之和视为 $0$。
• 如果中心下标位于数组最右端（第 $N$ 个位置），则右侧数之和视为 $0$。

请输出这个中心下标 $P$。 注意：

1. 本题采用 1-based 索引（下标从 1 开始）。
2. 如果有多个中心下标，输出最靠左的那一个。
3. 如果不存在这样的下标，输出 $-1$。

输入格式

第一行包含一个整数 $N$，表示数组的长度。 第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$，表示数组元素。

输出格式

输出一行一个整数，代表中心下标 $P$（从 1 开始）。如果不满足条件，输出 -1。

数据范围

• $1 \le N \le 10^5$
• $-1000 \le A_i \le 1000$
• 保证计算过程中的数值在 32 位有符号整数范围内。

样例输入 1

6
1 7 3 6 5 6

样例输出 1

4

样例解释 1

• 下标 4 对应的数值是 6。
• 左侧和：$A_1 + A_2 + A_3 = 1 + 7 + 3 = 11$。
• 右侧和：$A_5 + A_6 = 5 + 6 = 11$。
• $11 = 11$，且 4 是第一个满足条件的，故输出 4。

样例输入 2

3
1 2 3

样例输出 2

-1

样例输入 3

3
2 1 -1

样例输出 3

1

(解释：下标 1 左侧和为 0，右侧和 1 + (-1) = 0。相等，故输出 1)

三、 标准代码 (C++14 OI风格)

/**
 * 题目：寻找平衡点
 * 知识点：前缀和思想，线性扫描
 * 时间复杂度：O(N) - 遍历两次数组
 * 空间复杂度：O(N) - 存储数组 (可优化至O(1)如果不存数组)
 */

#include <iostream>
#include <vector>
#include <numeric> // 用于 accumulate 求和

using namespace std;

// 建议使用 long long 防止累加溢出，尽管本题数据范围 int 也可以
typedef long long ll;

const int MAXN = 100005;
int a[MAXN]; // 全局数组

int main() {
    // 1. IO 优化
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    // 2. 读入数据并计算总和
    // 使用 totalSum 记录所有元素的和
    ll totalSum = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        totalSum += a[i];
    }

    // 3. 线性扫描寻找平衡点
    // leftSum 动态记录当前位置左边的元素之和
    ll leftSum = 0;

    for (int i = 1; i <= n; ++i) {
        // 核心推导公式：
        // 右边和 = 总和 - 左边和 - 当前元素
        // 若 左边和 == 右边和，则：
        // 左边和 == 总和 - 左边和 - 当前元素
        // => 2 * 左边和 + 当前元素 == 总和
        
        if (2 * leftSum + a[i] == totalSum) {
            cout << i << endl; // 找到最靠左的解，直接输出并结束
            return 0;
        }

        // 当前位置检查完毕，将其加入 leftSum，为检查下一个位置做准备
        leftSum += a[i];
    }

    // 4. 如果循环结束仍未找到
    cout << -1 << endl;

    return 0;
}

四、 教学备课重点 (教练参考)

1. 公式推导能力：

   • 本题的关键不在于写出复杂的算法，而在于先数学推导，再代码实现。
   • 引导学生在草稿纸上画图，推导出 2 * leftSum + nums[i] == totalSum 这个公式。这是将 $O(N^2)$ 降维到 $O(N)$ 的关键一步。

2. 边界处理：

   • 左边界：当 $i=1$ 时，leftSum 初始为 0，这符合题目“左侧没有元素视为 0”的定义。
   • 右边界：公式推导自然涵盖了 $i=N$ 的情况，此时 RightSum 计算结果会自动为 0。
   • 负数情况：题目数据包含负数，但这不影响等式的成立，无需特殊处理，但要提醒学生不要因为直觉认为“越加越大”而手动剪枝（例如 leftSum > totalSum 就退出是错误的，因为后面可能有负数）。

3. 空间优化：

   • 上面的标准代码存储了数组 a[]。实际上，如果对空间要求极致，我们甚至可以不存数组（如果题目允许读两遍流，或者如果只用 totalSum - leftSum - currentVal == leftSum 逻辑）。但在 CSP-J 级别，开一个 $10^5$ 的数组是标准操作，代码可读性更好。

4. 与前缀和模板的区别：

   • 上一题（区域和检索）我们显式构建了 preSum[] 数组。
   • 这一题我们使用了一个动态变量 leftSum 来模拟前缀和。这展示了前缀和思想的另一种形态：边遍历边累加。