[Daimayuan] 吃糖果（C++，贪心）

贪心）"/>

[Daimayuan] 吃糖果（C++，贪心）

桌子上从左到右放着 n n n 个糖果。糖果从左到右编号，第 i i i 块糖果的重量为 w i w_i wi​。小明和小红要吃糖果。

小明从左边开始吃任意数量的糖果。（连续吃，不能跳过糖果）

小红从右边开始吃任意数量的糖果。（连续吃，不能跳过糖果）

当然，如果小明吃了某个糖果，小红就不能吃它（反之亦然）。

他们的目标是吃同样重量的糖果，请问此时他们总共最多能吃多少个糖果？

输入格式

第一行包含一个整数 n n n，表示桌上糖果的数量。

第二行包含 n n n 个整数 w 1 , w 2 , … , w n w_1,w_2,…,w_n w1​,w2​,…,wn​，表示糖果从左到右的重量。

输出格式

一个整数，表示小明和小红在满足条件的情况下总共可以吃的糖果的最大数量。

数据范围

1 ≤ n ≤ 2 ∗ 1 0 5 , 1 ≤ w i ≤ 1 0 4 1≤n≤2*10^5,1≤w_i≤10^4 1≤n≤2∗105,1≤wi​≤104

输入样例

9
7 3 20 5 15 1 11 8 10

输出样例

7

解题思路

采用贪心算法（不断尝试吃更多的糖）解决此题：

初始化规定糖的重量相等，然后循环分支：

（1）糖的重量相等，记录当前总共吃了多少颗糖，双方再吃一颗糖；

（2）糖的重量不相等，吃的少的一方再吃一颗糖。

结束条件：双方吃糖发生冲突（题目规定：“如果小明吃了某个糖果，小红就不能吃它（反之亦然）”）。

AC代码如下：

#include <iostream>
using namespace std;
const int max_n = 2e5;
const int max_w = 1e4;int candies[max_n];int main() {int n;cin >> n;for (int i = 0; i < n; i++) cin >> candies[i];int l = 0, r = n - 1, l_sum = 0, r_sum = 0, ans = 0;while (l < r) {if (l_sum == r_sum) {ans = l - 0 + n - 1 - r;l_sum += candies[l++];r_sum += candies[r--];}else if (l_sum < r_sum) l_sum += candies[l++];else r_sum += candies[r--];}cout << ans << endl;return 0;
}

贪心证明：

初始化，规定双方吃糖量相同，吃糖数目为 0 0 0。

为了确定是否存在比 0 0 0大的解，我们必须要让其中一方吃一颗糖。

那么这就会导致双方吃糖量不等，要让其相等，我们必须让另一方吃一颗糖。

只要不平衡，我们就需要让吃的少的那一方继续吃。

当平衡的时候，设吃糖数目为 a n s ans ans。

为了确定是否存在比 a n s ans ans大的解，我们必须要让其中一方吃一颗糖…（依次类推，直到发生冲突）