# U397461 平衡划分 ## 题目描述 体育课一共有 $N$ 名同学，且同学们排成一队，每个同学都有一个体力值 $A_i$ 。 所以同学们可以被看做一个含有 $N$ 个正整数的序列 $A_1,A_2,\ldots,A_N$ 。 现在老师要带大家做游戏了，游戏需要分为把同学们分为三组，为了游戏的公平性，需要每组同学的体力值之和都完全一致， 并且每组组内的同学的位置要为连续的一段。 换句话说，你需要选择两个整数 $L,R$ ，使得 $A_1$ 到 $A_L-1$ 的和等于 $A_L$ 到 $A_R$ 的和 等于 $A_R+1$ 到 $A_N$ 的和 , $(2\le L \le R \le N-1)$ 请问老师能否完成一个公平的分组？ ## 输入格式 第一行一个正整数 $T$，表示数据组数。 对于每一组数据，第一行输入一个正整数 $N$，表示序列长度。 第二行输入 $N$ 个正整数 $A_1, A_2, \ldots, A_N$，含义见题面。 ## 输出格式 可以则输出`YES` ,否则输出`NO` ## 输入输出样例 #1 ### 输入 #1 ```

这道题可以通过前缀和来高效解决。我们需要找到两个分割点L和R，使得整个数组被分成三个部分，每个部分的和相等。 解题思路 1. 计算整个数组的总和sum。如果sum不能被3整除，直接返回NO。 2. 计算每个部分的目标值target = sum / 3。 3. 使用前缀和数组快速计算区间和。 4. 遍历数组，记录所有能到达第一个target的位置（即前缀和等于target的位置）。 5. 在这些位置之后，继续寻找前缀和等于2*target的位置（即第二个分割点）。 C++代码实现 ```cpp #include <iostream> #include <vector> using namespace std; void solve() { int N; cin >> N; vector<int> A(N); long long sum = 0; for (int i = 0; i < N; ++i) { cin >> A[i]; sum += A[i]; } if (sum % 3 != 0) { cout << "NO" << endl; return; } long long target = sum / 3; vector<int> possible_L; long long prefix = 0; for (int i = 0; i < N - 2; ++i) { prefix += A[i]; if (prefix == target) { possible_L.push_back(i + 1); // L is i+2 in 1-based } } if (possible_L.empty()) { cout << "NO" << endl; return; } prefix = 0; bool found = false; for (int i = 0; i < N; ++i) { prefix += A[i]; if (i >= possible_L[0] && prefix == 2 * target && i < N - 1) { found = true; break; } } cout << (found ? "YES" : "NO") << endl; } int main() { int T; cin >> T; while (T--) { solve(); } return 0; } ``` 代码解释 1. 输入处理：读取数组并计算总和sum。 2. 初步判断：如果sum不能被3整除，直接输出NO。 3. 寻找第一分割点：遍历数组，记录所有前缀和等于target的位置（即可能的L值）。 4. 寻找第二分割点：在这些可能的L值之后，继续寻找前缀和等于2*target的位置（即R值）。 5. 输出结果：如果找到满足条件的L和R，输出YES，否则输出NO。 注意事项 1. 数组索引的处理要小心，特别是在1-based和0-based之间转换时。 2. 总和可能很大，使用long long类型避免溢出。 3. 在寻找第二分割点时，确保R的位置在L之后且不是最后一个元素。 额外逻辑点 1. 确保总和能被3整除是快速判断的基础条件。 2. 第一分割点L必须保证后面还有至少两个元素（R和最后一部分）。 3. 第二分割点R必须保证后面还有至少一个元素（最后一部分）。 [2025-06-18 19:19:39 | AI写代码神器 | 692点数解答]