题目解析
* 输入输出:第一行输入整数 ttt 表示测试用例组数。每组数据包含:一行整数 nnn 表示序列长度,一行 nnn 个正整数表示序列。对每组数据输出 Yes 表示存在位置 iii(1<i<n1 < i < n1<i<n)使得前 iii 个元素之和等于剩余元素之和,否则输出 No。
* 数据范围:1≤t≤1001 \le t \le 1001≤t≤100,1≤n,ai≤100001 \le n, a_i \le 100001≤n,ai ≤10000。多组数据总规模适中,单个序列长度不超过 10410^4104。
* 复杂度要求:每组数据需要 O(n)O(n)O(n) 时间处理,总时间复杂度 O(t⋅n)≤106O(t \cdot n) \le 10^6O(t⋅n)≤106,符合 1s 限制;空间复杂度 O(n)O(n)O(n) 存储序列。
* 算法知识点:前缀和、后缀和、双指针、枚举
思路解析
1. 总和初始化:首先遍历序列计算所有元素的总和,记为 right_sum,表示当前分割点右侧所有元素的和(初始时右侧为整个序列)。
2. 同步维护左右和:从左到右遍历序列(分割点 iii 从 111 到 n−1n-1n−1),每次将当前元素 aia_iai 从 right_sum 中减去(右侧不再包含该元素),并加入 left_sum(左侧包含该元素)。这样 left_sum 始终表示前 iii 个元素的和,right_sum 表示第 i+1i+1i+1 到第 nnn 个元素的和。
3. 平衡判定:在每一步更新后,检查 left_sum 与 right_sum 是否相等。若相等,说明找到一个合法分割点,立即输出 Yes 并结束当前测试用例。
4. 未找到处理:若遍历完所有可能的分割点(iii 从 111 到 n−1n-1n−1)均未发现相等的情况,输出 No。
5. 精度处理:使用 long long 存储和值,防止多个 10410^4104 级别数值累加导致 int 溢出(虽然题目范围内 104×104=10810^4 \times 10^4 = 10^8104×104=108 在 int 范围内,但这是良好的 defensive programming 习惯)。
完整代码