贪心算法:排列算式

这篇具有很好参考价值的文章主要介绍了贪心算法:排列算式。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述

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

贪心算法:排列算式,C++,贪心算法,算法,c++文章来源地址https://www.toymoban.com/news/detail-849258.html

到了这里,关于贪心算法:排列算式的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 力扣--深度优先算法/回溯算法47.全排列 Ⅱ

    思路分析: 使用DFS算法进行全排列,递归地尝试每个可能的排列方式。 使用 path 向量保存当前正在生成的排列,当其大小达到输入数组的大小时,将其加入结果集。 使用 numvisited 向量标记每个数字是否已经被访问过,以确保每个数字在一个排列中只使用一次。 在递归过程中

    2024年03月13日
    浏览(51)
  • 递归算法学习——全排列

    目录 ​编辑 一,问题描述 1.例子: 题目接口:  二,问题分析和解决 1.问题分析 2.解题代码 首先我们得来先看看全排列的问题描述。全排列问题的问题描述如下: 给定一个不含重复数字的数组  nums  ,返回其  所有可能的全排列  。你可以  按任意顺序  返回答案。 1.例

    2024年02月11日
    浏览(40)
  • 回溯算法篇-01:全排列

    这道题属于上一篇——“回溯算法解题框架与思路”中的 “元素不重复不可复用” 那一类中的 排列类问题。 我们来回顾一下当时是怎么说的: 排列和组合的区别在于,排列对“顺序”有要求。比如 [1,2] 和 [2,1] 是两个不同的结果。 这就导致了同一个元素 在同一条路径中不

    2024年01月20日
    浏览(32)
  • 算法--排列组合

    2024年02月16日
    浏览(39)
  • java实现排列组合算法

    我这里只写了组合的算法。         假设现有 M=4 个数据 a,b,c,d。从中随机抽取n个数,n为1—4个数据进行组合。那么数学中的计算组合方式为C(4,1) + C(4,2) + C(4,3) + C(4,4)  = 4 + 6 + 4 + 1 = 15。那么共有15种组合方式。 方案一:此方法容易理解但是效率慢         我的做

    2024年02月13日
    浏览(49)
  • 【算法题】47. 全排列 II

    给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。 示例 1: 输入:nums = [1,1,2] 输出: [[1,1,2],  [1,2,1],  [2,1,1]] 示例 2: 输入:nums = [1,2,3] 输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]   提示: 1 = nums.length = 8 -10 = nums[i] = 10 来自力扣官方题解

    2024年02月01日
    浏览(62)
  • 什么是全排列?(算法实现)

    全排列是指将一组元素按照一定顺序进行排列的所有可能结果。以一组数字为例,比如[1, 2, 3]的全排列结果为:[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]。 全排列有许多不同的计算方法,其中最常用的方法之一是使用递归。可以通过递归函数来实现全排列,每次从剩

    2024年02月07日
    浏览(32)
  • 【算法Hot100系列】全排列

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年01月18日
    浏览(101)
  • 算法第二期——排列组合(Python)

    目录 排列函数permutations( ) 易错点 组合函数combinations( ) 手写排列和组合代码  1.暴力法/

    2023年04月18日
    浏览(36)
  • 【算法教程】排列与组合的实现

    在讲排列与组合之前,我们先定义数据元素类型Fruit 对N个不同元素进行排序,总共有多少不同的排列方式? 例子:某水果店有以下水果,请对所有水果进行全排列,请输出所有排列 排列算法的javascript实现模板(DSF,最优解in-place) 测试结果 对N个不同元素进行排序,总共有多少不

    2024年02月07日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包