分糖果——牛客

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

题目描述

幼儿园准备了nnn包糖果，每包糖果里有111、222或333颗美味的糖果。现在需要将这些这些糖果平分给两个表现优异的小朋友以作奖励，为了公平公正，需要确保两位小朋友分得的糖果颗数相等，且每一包糖果都需要分给正好一位小朋友。幼儿园园长委托你帮忙判断下：是否存在可行的分配方法？

输入描述:

输入共两行。
第一行一个整数n(1≤n≤2×105)表示糖果的包数。
第二行n个整数，第i个整数ai(1≤ai≤3)表示第i包中糖果的数量。

输出描述:

如果存在可行的分配方案，则输出"YES"；否则输出"NO"。

示例1

输入

5
1 3 3 2 1

输出

复制YES

YES

示例2

输入

4
3 1 3 3

输出

复制NO

NO

思路：

先看我一开始最先想到的代码

#include <iostream>
using namespace std;
int cnt[4];
int main() {int n;cin >> n;int a[n];for(int i = 0; i < n; i ++) {cin >> a[i];cnt[a[i]] ++;}cnt[3] %= 2;if(cnt[3] == 1) {if(cnt[2] > 0 && cnt[1] > 0) {cnt[3] = 0;cnt[2] --;cnt[1] --;}if(cnt[3] == 1 && cnt[1] >= 3) {cnt[3] = 0;cnt[1] -= 3;}}if(cnt[3] != 0) {cout << "NO";return 0;}cnt[2] %= 2;if(cnt[2] == 1) {if(cnt[1] >= 2) {cnt[2] = 0;cnt[1] -= 2;}}if(cnt[2] != 0) {cout << "NO";return 0;}cnt[1] %= 2;if(cnt[1] == 1) {cout << "NO";return 0;}cout << "YES";return 0;
}

这样写并不能够AC,我认为原因就是没有考虑全部的情况。糖果数目一共三种，1，2，3。而解题的思路在于“抵消”，3和3可以抵消，3和2+1可以抵消，3和1+1+1可以抵消。2和1+1可以抵消。但同样的2+2+2和3+3也可以抵消。比如输入【2,2,2,3,3】时代码就会计算错误，所以需要把这个情况排除掉。

#include <iostream>
using namespace std;
int cnt[4];
int main() {int n;cin >> n;int a[n];for(int i = 0; i < n; i ++) {cin >> a[i];cnt[a[i]] ++;}while(cnt[2] >= 3 && cnt[3] >= 2 && cnt[2] > cnt[3]) {cnt[2] -= 3;cnt[3] -= 2;}cnt[3] %= 2;if(cnt[3] == 1) {if(cnt[2] > 0 && cnt[1] > 0) {cnt[3] = 0;cnt[2] --;cnt[1] --;}if(cnt[3] == 1 && cnt[1] >= 3) {cnt[3] = 0;cnt[1] -= 3;}}if(cnt[3] != 0) {cout << "NO";return 0;}cnt[2] %= 2;if(cnt[2] == 1) {if(cnt[1] >= 2) {cnt[2] = 0;cnt[1] -= 2;}}if(cnt[2] != 0) {cout << "NO";return 0;}cnt[1] %= 2;if(cnt[1] == 1) {cout << "NO";return 0;}cout << "YES";return 0;
}