[Daimayuan] 弗拉德和糖果 II（C++，数学）

不久前，弗拉德过生日，他收到了一包糖果。有 $n$ 种糖果，第 $i$ 种糖果有 aia_iai​ 个（$1\le i\le n$）。

弗拉德决定每次只吃一个糖果。为了从吃东西中获得最大的乐趣，弗拉德不想连续吃两个相同类型的糖果。

帮助他弄清楚他是否可以在不连续吃两个相同的糖果的情况下吃掉所有的糖果。

简而言之，给定 $n$ 个正整数 aia_iai​，aia_iai​ 表示有 aia_iai​ 个 $i$，找到是否存在一种序列，使得所有的数都用上，且不存在 $i$ 连续的情况

输入格式：

第一行，包含一个整数 $n$。 第二行，包含 $n$ 个正整数。

输出格式:

输出一行，如果存在，输出YES，否则输出NO

样例输入

2
1 1

样例输出

YES

说明

只有两种情况：

1 2

2 1

无论先吃哪种糖果，都能吃完且不连续吃相同类型的糖果

数据限制

对于 $100\%$ 的数据，保证 1≤n≤5000000,1≤ai≤2301≤n≤5000000,1≤a_i≤2^{30}1≤n≤5000000,1≤ai​≤230

解题思路：

因为要求不能连续吃相同的糖果，所以我们预先把相同糖果间留出空隙

我们只关心糖果之间的空隙能否被填充，并不关心之前或者之后有没有其他糖果，也不关心空隙之间到底有多少颗糖果

那么假设在吃aia_iai​糖果之前，已经排好了$sum$颗糖果

（1）如果有sum≥ai−1sum \\ge a_i - 1sum≥ai​−1，则可以顺利吃掉aia_iai​糖果（空隙可以填充），同时更新$sum$，回到（1）

（2）但是如果条件不成立，那么我们就会剩下ai−sum−1a_i-sum-1ai​−sum−1颗糖果等待被吃

（3）然后我们接收下一个输入ai+1a_{i+1}ai+1​，如果ai+1a_{i+1}ai+1​大于剩余糖果数量，则可以顺利吃掉aia_iai​糖果；反之更新剩余糖果数量和$sum$后回到（3）等待下一次输入

（4）在顺利吃掉aia_iai​糖果之后，要判断ai+1a_{i+1}ai+1​是否能被吃掉，能的话回到（1），反之回到（3）

注：当sum > max_a的时候，无论接下来的输入糖果数量是多少，我们都可以吃掉，所以不用继续累计$sum$，也就不用担心爆精度问题

AC代码如下

#include <stdio.h>
#include <stdlib.h>
const int max_n = 5e6;
const long long max_a = 2ll << 30;int main() {int n;scanf("%d", &n);long long a, sum = 0, buffer = 0;for (int i = 0; i < n; i++) {scanf("%lld", &a);if (sum <= max_a) {if (!buffer) {if (sum >= a - 1) sum += a;//(1)else {//(2)sum = sum * 2 + 1;buffer = a - sum - 1;}}else {//(3)if (a >= buffer) {sum += buffer;if (sum >= a - 1) {sum += a;buffer = 0;//return (1)}else {sum = sum * 2 + 1;buffer = a - sum - 1;//return (3)}}else {buffer -= a;sum += 2 * a;}}}}if (sum > max_a || !buffer) printf("YES");else printf("NO");return 0;
}