题目描述
给出n数字，对于这些数字是否存在一种计算顺序，使得计算过程中数字不会超过3也不会小于0？
输入描述:
首行给出一个正整数t,(1≤t≤1000)代表测试数据组数
每组测试数据第一行一个正整数n,(1≤n≤500)
第二行包含n个以空格分隔的数字
输入保证每一个数字都是 −3, −2, −1, +0, +1, +2, +3 的其中一个。
输出描述:
每组测试数据输出一行，“Yes” or “No”
输入
2
4
+3 +2 -1 -2
5
+3 +2 +1 +0 +2
输出
Yes
No
说明
第一组依照 +3,−2,+2,−1 的顺序由左至右计算总和，过程会依序算得 3, 1, 3, 2，满足题目要求
很显然第二组不存在满足要求的计算顺序
#include <bits/stdc++.h> #include<iostream> using namespace std; int N, n, a[7], *cnt; bool check() { int t = 0; for (int i = -3; i <= 3; i++) { t += i * cnt[i]; } if (t > 3 || t < 0) return false; t = min(cnt[-3], cnt[3]); cnt[-3] -= t; cnt[3] -= t; t = min(cnt[2], cnt[-1]); cnt[2] -= t; cnt[-1] -= t; cnt[1] += t; t = min(cnt[-3], cnt[1]); cnt[-3] -= t; cnt[1] -= t; cnt[-2] += t; if (cnt[-3] > 0) return false; t = min(cnt[-2], cnt[1]); cnt[-2] -= t; cnt[1] -= t; cnt[-1] += t; t = min(cnt[3], cnt[-1]); cnt[3] -= t; cnt[-1] -= t; cnt[2] += t; if (cnt[3] > 1) return false; return true; } int main() { cin>>N; cnt = &a[3]; while (N--) { memset(a, 0, sizeof(a)); cin>>n; int t; for (int i = 1; i <= n; i++) { cin>>t; cnt[t]++; } if (check()) { cout<<"Yes\n"; } else { cout<<"No\n"; } } return 0; }
