体育课同学体力值平衡划分：利用前缀和高效解题

这道题可以通过前缀和来高效解决。我们需要找到两个分割点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必须保证后面还有至少一个元素（最后一部分）。 ######[AI写代码神器 | 692点数解答 | 2025-06-18 19:19:39]