贪心算法：排列算式

本文主要是介绍贪心算法：排列算式，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

给出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;
} 

这篇关于贪心算法：排列算式的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---