喵~ 主人，你好呀~ ฅ'ω'ฅ

今天我们来看一道关于吃糖果的有趣问题，喵~ Alice 和 Bob 要比赛吃糖果，但他们又想很公平，真是的，吃个糖果也这么讲究，哼哼~ 不过没关系，就让本猫娘来帮他们找到最好的办法吧！

题目大意

题目是这样的喵：有一排 n 颗糖果，每颗糖果都有自己的重量。

• Alice 从最左边开始吃，不能跳过，只能连续吃。
• Bob 从最右边开始吃，同样不能跳过，只能连续吃。
• 他们俩吃过的糖果不能是同一颗哦！

他们的目标是，在两个人吃掉的糖果总重量相等的情况下，吃掉尽可能多的糖果。我们要找的就是这个最大的糖果总数，的说。

题解方法

看到这种从两头向中间靠拢的问题，本猫娘的直觉就告诉我，可以用 “双指针” 来解决！呐，就像两只小猫从长长的鱼干两头开始吃一样，嘿嘿~

我们可以设置两个指针，一个叫 i_ptr 指向 Alice 已经吃到的最后一颗糖，从左边开始；另一个叫 j_ptr 指向 Bob 已经吃到的最后一颗糖，从右边开始。再用两个变量 left_sum 和 right_sum 分别记录 Alice 和 Bob 已经吃掉的糖果的总重量。

我们的策略是这样的喵：

1. 一开始，Alice 和 Bob 都还没吃，所以 left_sum 和 right_sum 都是 0。
2. 我们让两个指针不断向中间移动，直到它们相遇或者交错过去。
3. 在移动的过程中，我们比较 left_sum 和 right_sum：
   • 如果 left_sum < right_sum，说明 Alice 吃得太少啦，为了追上 Bob，Alice 就得再吃一颗左边的糖果。所以 i_ptr 向右移动，并把新吃的糖果重量加到 left_sum 上。
   • 如果 left_sum > right_sum，这次轮到 Bob 吃得少啦，Bob 就得再吃一颗右边的糖果。所以 j_ptr 向左移动，并把新吃的糖果重量加到 right_sum 上。
   • 哦哦！如果 left_sum == right_sum，太棒了喵！我们找到了一个公平的方案！这时候，他们吃的总糖果数就是 Alice 吃的数量加上 Bob 吃的数量。我们要记录下这个数量，因为它可能是最终的答案。然后呢？为了找到可能存在的、吃更多糖果的方案，我们还得继续呀。可以让 Alice 再吃一颗（当然 Bob 也行），打破这个平衡，继续我们的寻找之旅~

只要左指针还在右指针的左边，我们就一直重复这个过程。每次发现 left_sum 和 right_sum 相等时，就更新我们记录的最大糖果数。当指针相遇时，游戏结束，我们找到的就是最优解啦！是不是很简单喵？

题解

下面就是具体的代码实现啦，主人请看~

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> w(n);
        for (int i = 0; i < n; i++) {
            cin >> w[i];
        }

        long long left_sum = 0, right_sum = 0;
        int i_ptr = -1, j_ptr = n; // 指针初始化
        int ans = 0;

        while (i_ptr < j_ptr) { // 只要两个指针没有相遇或交错
            if (left_sum == right_sum) {
                // 找到一个有效状态，更新答案
                ans = (i_ptr + 1) + (n - j_ptr);
            }

            if (left_sum <= right_sum) {
                // Alice 的重量和小于等于 Bob，Alice 吃下一颗
                i_ptr++;
                if (i_ptr < j_ptr) { // 确保还有糖果可以吃
                    left_sum += w[i_ptr];
                } else {
                    break; // 糖果吃完了，跳出循环
                }
            } else {
                // Bob 的重量和较小，Bob 吃下一颗
                j_ptr--;
                if (i_ptr < j_ptr) { // 确保还有糖果可以吃
                    right_sum += w[j_ptr];
                } else {
                    break; // 糖果吃完了，跳出循环
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

代码解释喵~

1. i_ptr 初始化为 -1，j_ptr 初始化为 n。这是一种很方便的写法，i_ptr + 1 就代表 Alice 吃了多少颗糖，n - j_ptr 就代表 Bob 吃了多少颗糖。一开始都是 0，很合理对吧！
2. while (i_ptr < j_ptr) 是循环的核心。只要 i_ptr 和 j_ptr 之间还有没被分配的糖果，循环就继续。
3. if (left_sum == right_sum)：当两边的重量和相等时，我们就找到了一个可能的答案。此时 Alice 吃了 i_ptr + 1 颗，Bob 吃了 n - j_ptr 颗，总数就是 (i_ptr + 1) + (n - j_ptr)。我们用 ans 变量把它记下来。
4. if (left_sum <= right_sum)：这里是关键的贪心选择。如果 Alice 的总重量小于或等于 Bob 的，就让 Alice 吃下一颗。i_ptr++，然后把 w[i_ptr] 加到 left_sum。注意哦，当 left_sum == right_sum 时，也是 Alice 先吃，这样可以打破平衡，继续寻找下一个可能的相等状态。
5. else：如果 Alice 的总重量更大，那就该 Bob 吃啦。j_ptr--，然后把 w[j_ptr] 加到 right_sum。
6. 循环里的 if (i_ptr < j_ptr) 是为了防止指针越界。比如当 Alice 吃完最后一颗糖后，i_ptr 会等于 j_ptr - 1。如果此时 left_sum 仍然小于等于 right_sum，Alice 会尝试再吃一颗，i_ptr 就会变成 j_ptr，这时候就不能再取 w[i_ptr] 了，因为那颗糖可能已经被 Bob 占有或者根本不存在了，所以要 break。
7. 最后输出 ans 就好啦，它保存了整个过程中找到的最大的糖果数，的说。

知识点介绍

嘿嘿，这道题背后其实藏着一些很有用的知识点哦，让本猫娘来给你讲讲~

1. 双指针 (Two Pointers) 喵

双指针是一种超级棒的算法技巧！它通常用在数组或者序列上，通过维护两个指针，一个从头开始，一个从尾开始，然后让它们相向移动，来解决问题。就像我们这道题里 Alice 和 Bob 一样~

• 优点：它能把一些需要嵌套循环（通常是 O(n²) 复杂度）的问题，优化到只需要一次遍历（O(n) 复杂度），效率超高！因为每个元素最多只被一个指针访问一次。
• 应用场景：除了这道题，双指针还经常用在：
  • 在有序数组中寻找和为定值的两个数。
  • 反转字符串或数组。
  • 寻找最长不重复子串。
  • 等等很多地方，是一个非常基础但强大的工具呢！

2. 贪心算法 (Greedy Algorithm) 喵

我们这道题的解法，其实也体现了贪心思想。所谓贪心，就是在每一步都做出当前看起来最好的选择，期望通过一系列局部最优解，最终能得到全局最优解。

在这里，我们的“贪心选择”就是：总是让当前总重量较小的一方吃下一颗糖。

为什么这个贪心是正确的呢？喵~ 我们可以这样想：假设我们已经有了一个平衡状态（left_sum == right_sum），总共吃了 k 颗糖。如果我们想找到一个吃掉 k' > k 颗糖的更好方案，那么这个新方案一定是在当前方案的基础上，让 Alice 和/或 Bob 再多吃几颗糖。我们的策略——让总和少的一方吃糖——正是为了不断扩大已吃的糖果范围，去探索这些可能存在的更好方案。因为我们总是在逼近下一个可能的平衡点，所以不会错过任何一个潜在的最优解。这个过程保证了我们能找到最大的糖果数，真是太聪明了，喵！

---

好啦~ 这道题的讲解就到这里啦！主人有没有觉得豁然开朗呢？用双指针和一点点贪心的小智慧，就能轻松解决问题啦！下次再遇到类似的问题，可要想起本猫娘的讲解哦~ 喵~ ฅ(>ω<*)ฅ