咕咕东想吃饭

问题描述

咕咕东考试周开始了，考试周⼀共有n天。他不想考试周这么累，于是打算每天都吃顿好的。他决定每天都吃生煎，咕咕东每天需要买ai个生煎。
但是生煎店为了刺激消费，只有两种购买⽅式：
①在某⼀天⼀次性买两个生煎。
②今天买⼀个生煎，同时为明天买⼀个生煎，店家会给⼀个券，第⼆天用券来拿。
没有其余的购买方式，这两种购买方式可以用无数次。但是咕咕东是个节俭的好孩⼦，他考试结束就走了，不允许考试结束时手里有券。咕咕东非常有钱，你不需要担心咕咕东没钱，但是咕咕东太笨了，他想问你他能否在考试周每天都能恰好买ai个生煎。

Input

输⼊两⾏，第⼀行输⼊⼀个正整数 n (1 ≤ n ≤ 100000)，表示考试周的天数。
第⼆行有n个数，第i个数ai表示第i天咕咕东要买的生煎的数量。

Output

如果可以满足咕咕东奇怪的要求，输出"YES"，如果不能满足，输出“NO”。（输出不带引号）

Sample

Input: 
4 1 2 1 2 
Output: 
YES

Input: 
3 1 0 1
Output: 
NO

Limitation

Time limit		1000 ms
Memory limit	262144 kB

数据范围

数据点	n (上限)	ai (上限)
1, 2	10	≤ 10
3, 4, 5	1000	10
6, 7	10	10000
8, 9, 10	100000	10000

解题思路

比较容易，一个for循环再几个if条件判断就行了，复杂度O(n)。

每天都有两种选择，选择根据今天应该有的生煎数来选，初始时昨天预留的生煎数remain = 0，之后若有预留，则remain = 1。则 今日想买的生煎数 - remain 就是 今日应该要买的生煎数。
这两种选择，根据今日应买数量是否为2的倍数来判断，是则预留为0，否则预留为1。然后根据最后一天的剩余量判断就行。
这题比较容易出错的是0(题目说好的明明“决定每天都吃生煎”呢🤔🤨😐😑😶🙄)，还好样例2有给个0，不然我还真不会去考虑0的情况……若前一天有剩但今日为0，直接终止循环，输出NO。

源代码

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
	int* arr = new int[n];
	int remain = 0;//当日剩余生煎数
	bool failed = false;//不能满足？
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	for (int i = 0; i < n; i++) {
		int a = arr[i] - remain;//扣去前一天剩下的券(如果有) 今天还有的生煎数
		if (a < 0) {//昨天有剩券 但今天不想吃
			failed = true;//不能满足
			break;
		}

		if (a % 2 == 0)//今天不需要买 券那个方案，选方案一
			remain = 0;
		if (a % 2 == 1)//需要买张券，选方案二
			remain = 1;
	}
	if (remain == 0 && failed == false)//最后一天 没剩 且 之前都满足
		cout << "YES" << endl;
	if (remain == 1 || failed == true)//最后一天有剩 或 之前某天不满足
		cout << "NO" << endl;

	return 0;
}