题目描述
给出n数字,对于这些数字是否存在一种计算顺序,使得计算过程中数字不会超过3也不会小于0?文章来源:https://www.toymoban.com/news/detail-849258.html
输入描述:
首行给出一个正整数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;
}
文章来源地址https://www.toymoban.com/news/detail-849258.html
到了这里,关于贪心算法:排列算式的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!