[Daimayuan] 吃糖果（C++，贪心）-Toy模板网

这篇具有很好参考价值的文章主要介绍了[Daimayuan] 吃糖果（C++，贪心）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

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

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

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

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

输入格式

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

第二行包含 $n$ 个整数 $w_1,w_2,…,w_n$ ，表示糖果从左到右的重量。

输出格式

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

数据范围

$1≤n≤2*10^5,1≤w_i≤10^4$

输入样例

9
7 3 20 5 15 1 11 8 10

输出样例

解题思路

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

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

（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;
}