当前位置: 首页 > news >正文

[牛客习题]“幸运的袋子”

习题链接:幸运的袋子_牛客题霸_牛客网

题目分析

 由题意可知:“幸运的袋子”的概念是——小球的数值之和大于小球的数值之积。

假如现在有5个小球:1,1,3,5,7,并将他们编号a0~a4.我们现在来看其中一种满足“幸运”条件的情况:我们设置变量sum来记录数值之和,用multi来记录数值之积,用count来记录袋子数量。

 我们先取a0这个小球,数值为1。接着取a1——(1+1)>(1*1),满足条件,计数器count+1.我们继续取a2——(1+1+3)>(1*1*3),满足条件,计数器count+1.

接着我们取a3,(1+1+3+5+7)<(1*1*3*5*7),不满足条件。那么我们就要回到上一层(取a2的那一层)来试试下一个取a4是否满足要求。

但是此时sum = (1+1+3+5+7) = 17,multi = 105,要想回到上一层就得sum减去刚拿到的a3,multi除以刚乘上的a3.然后去取a4,看看是否满足条件。

但是因为我们对数字进行递增排序了,如果a3不满足条件,那么a4也不会满足。

最后返回count的值。


如果我们写一个count函数,用来获得从取得某个球开始的“幸运袋子”的个数。对于n个小球来说,自小球a0开始的袋子个数为:小球a0与下一个小球ax之间袋子的个数 加上 以小球ax开始与ax的下一个小球之间的袋子个数 之和。然后依次递归

那么回到一个小球也没取的时候,此时为空(什么也没有),那么袋子的个数是不是 取第一个小球的个数(此时你取哪个小球都满足要求,因为此时就一个小球)加上 第一个小球与其取得下一个小球所有可能?

很好,现在我们总结出了其中的规律,现在我们来写代码


import java.util.*;
public class FortunatePackage {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();//输入小球的个数int[] a = new int[n];//将所有小球放入一个数组中,以数组下标为小球编号for (int i = 0; i < n; i++) {a[i] = sc.nextInt();}Arrays.sort(a);//将小球递增排序,以节省算力/*为什么要排序?仍然以(1,1,3,5,7)为例,当取到5时,5不满足要求,那么它后面的数都比它大,也一定不满足要求了*/System.out.println(count(a, n, 0, 0, 1));//从第一个下标开始取小球}/*pos是查找“幸运袋子”时的“第一个球的位置”,a[]是目前可供挑选的球,sum为和(初始值为0),multi为积(初始值为1),n为球的个数*/public static int count(int[] a,int n,int pos,int sum,int multi){int count = 0;for (int i = pos; i < n; i++) {sum += a[i];multi *= a[i];//如果这两个球满足“幸运袋子”的要求,“幸运袋子”的组合种类数为 1(这两个球组成的袋子)+ 剩下的所有球中存在的“幸运袋子”数if (sum > multi){count = count + 1 + count(a,n,i+1,sum,multi);}else if (a[i] == 1){count = count + count(a,n,i+1,sum,multi);}else {break;}//如果这两个球不满足“幸运袋子”的要求,则清除此次操作带来的数据改变,回溯到上一层sum -= a[i];multi /= a[i];//如果这个球不满足要求并且和下一个球的数值相等,则跳过下一个球的检测while (i < n-1 && a[i] == a[i+1]){i++;}}return count;}
}

相关文章:

[牛客习题]“幸运的袋子”

习题链接&#xff1a;幸运的袋子_牛客题霸_牛客网 题目分析 由题意可知&#xff1a;“幸运的袋子”的概念是——小球的数值之和大于小球的数值之积。 假如现在有5个小球&#xff1a;1&#xff0c;1&#xff0c;3&#xff0c;5&#xff0c;7&#xff0c;并将他们编号a0~a4.我们…...

安科瑞预付费系统在某大型连锁农贸市场的设计应用

安科瑞 崔丽洁 摘要 本远程预付费管理系统采用智能远程预付费电表&#xff08;DTSY1352-NK/DDSY1352-NK系列&#xff09;&#xff0c;NB智能远传水表&#xff0c;采集各商户实时用电量、用电量总数&#xff0c;通过平台定时结算&#xff0c;结算账户余额&#xff0c;从而进行智…...

Spring Boot Bean 注入的常用方式教程

Spring Boot Bean 注入是一种将依赖对象引入到应用程序组件中的机制&#xff0c;它有助于实现松耦合和可测试的代码。这种注入方式允许我们将依赖关系委托给 Spring 容器来管理&#xff0c;从而提高了代码的可维护性和可读性。Spring Boot 提供了多种 Bean 注入方式&#xff0c…...

Java项目调用Python脚本(基于idea)

前期准备 1.首先需要在本地环境中安装配置python环境 Python(含PyCharm及配置)下载安装以及简单使用(Idea) 博主本次使用python版本为py3.7.3 2.idea安装python插件 位置&#xff1a;File->Settings->Plugins->python->安装后重启即可 3.引入jython依赖 &l…...

前端 JS 经典:i,i++,++i区别

1. 概念 用于对变量进行自增操作。它们的区别在于返回值不同。 i 表示先使用 i 的值&#xff0c;再将 i 加 1&#xff0c;返回的是 i 自增前的值。 i 表示先将 i 加 1&#xff0c;再使用 i 的值&#xff0c;返回的是 i 自增后的值。 i 表示直接使用 i 的值&#xff0c;不进…...

EF Core 7.0 新特性之批量修改

概要 EF Core 7.0 提供了一个可以将LINQ查询和批量修改相结合的方法ExecuteUpdate。由于数据修改是以批量更新的方式完成&#xff0c;所以可以减少数据库的往返次数。 本文将主要介绍ExecuteUpdate的使用方法。 代码和实现 基本案例 本文我们使用银行分行&#xff0c;ATM机…...

Vue_Bug error0308010Cdigital envelope routinesunsupported

Bug描述&#xff1a; error0308010Cdigital envelope routinesunsupported 解决方法&#xff1a; Just add this to the top of vue.config.js : const crypto require(crypto);/*** md4 algorithm is not available anymore in NodeJS 17 (because of lib SSL 3).* In that…...

中科院提出“思维传播”,极大增强ChatGPT等模型复杂推理能力

中国科学院自动化研究所与耶鲁大学计算机系研究人员联合发布了&#xff0c;一份名为《思维传播:用大型语言模型进行基于类比的复杂推理》的论文。 ChatGPT等大型语言模型展示出了超强的创造能力&#xff0c;只需简单的文本提示就能生成小说、营销创意、简历等各种文本内容。但…...

ubuntu20.04安装opencv 3.2.0 报错

安装记录 Error 1: cmake时报错 CMake Error at cmake/OpenCVCompilerOptions.cmake:21 (else): A duplicate ELSE command was found inside an IF block. Fix: 修改opencv-3.2.0/cmake/OpenCVCompilerOptions.cmake文件 注释掉21和22行 else()message(STATUS "Unabl…...

KubeVela交付

有什么用我也不想说了&#xff0c;这个是k8s CI/CD,进阶玩家玩的了&#xff0c;比你们喜欢Arg CD更科学&#xff0c;更现代 在 Kubernetes 中安装 KubeVela helm repo add kubevela https://charts.kubevela.net/core helm repo update helm install --create-namespace -n v…...

【SpringCloud-10】SCA-nacos

前言&#xff1a; 前面介绍的springcloud&#xff0c;可以看做第一代&#xff0c;称为&#xff1a;SCN&#xff08;spring cloud Netflix&#xff09;; 接下来介绍的是第二代&#xff1a;SCA&#xff08;spring cloud alibaba&#xff09;&#xff1b; SCA主要有以下组件&#…...

卡顿分析与布局优化

卡顿分析与布局优化 大多数用户感知到的卡顿等性能问题的最主要根源都是因为渲染性能。Android系统每隔大概16.6ms发出VSYNC信 号&#xff0c;触发对UI进行渲染&#xff0c;如果每次渲染都成功&#xff0c;这样就能够达到流畅的画面所需要的60fps&#xff0c;为了能够实现60fp…...

【Vivado HLS Bug】Ubuntu环境下Vivado HLS导出IP报错:HLS ERROR: [IMPL 213-28]

Export IP Invalid Argument / Revision Number Overflow Issue (Y2K22) (xilinx.com)一.问题描述&#xff1a; 在Ubuntu20.04环境中使用Vivado HLS导出IP时报错&#xff1a;HLS ERROR: [IMPL 213-28] 二.解决方法&#xff1a; 1.从如下链接中下载官方补丁Export IP Invalid…...

2022最新版-李宏毅机器学习深度学习课程-P14 批次(batch)与动量(momentum)

一、batch 回顾epoch、shuffle batch size大还是小&#xff1f;都有好处 大batchsize的好处 由于GPU有并行计算的能力&#xff0c;左边并不一定用时更长 反而是&#xff0c;batch size小的时候&#xff0c;要跑完一个epoch所用的update时间更长&#xff0c;所以时间方面的比较…...

谜题(Puzzle, ACM/ICPC World Finals 1993, UVa227)rust解法

有一个5*5的网格&#xff0c;其中恰好有一个格子是空的&#xff0c;其他格子各有一个字母。一共有4种指令&#xff1a;A, B, L, R&#xff0c;分别表示把空格上、下、左、右的相邻字母移到空格中。输入初始网格和指令序列&#xff08;以数字0结束&#xff09;&#xff0c;输出指…...

acwing算法基础之数据结构--双链表

目录 1 知识点2 模板 1 知识点 一般的结构体写法为&#xff0c; struct BiListNode {int val;BiListNode *left;BiListNode *right; };但我们不用这个&#xff0c;而用数组模拟双链表&#xff0c;此时&#xff0c;用编号为0的结点表示头结点&#xff0c;用编号为1的结点表示尾…...

将中文名格式化输出为英文名

要求&#xff1a; 编写Java程序&#xff0c;输入样式为&#xff1a;Zhong wen ming的人名&#xff0c;以 Ming,Zhong.W 的形式打印出来。其中.W是中间单词的首字母&#xff1b;例如输入”Willian Jefferson Clinton“,输出形式为&#xff1a;Clinton,Willian.J public static …...

设计模式_迭代器模式

迭代器模式 介绍 设计模式定义案例迭代器模式行为型&#xff1a;关注对象与行为的分离 提供了一种统一的方式来访问多个不同的集合两个集合&#xff1a;使用了不同的数据存储方式 学生 和 警察 查询显示出集合的内容 &#xff0c;使用相同的代码 问题堆积在哪里解决办法不同…...

【数据结构】:栈的实现

1 栈 1.1栈的概念及结构 栈&#xff1a;一种特殊的线性表&#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶&#xff0c;另一端称为栈底。栈中的数据元素遵守后进先出LIFO&#xff08;Last In First Out&#xff09;的原则 压栈…...

微前端一:技术选型

微前端是一种多个团队通过独立发布功能的方式来共同构建现代化 web 应用的技术手段及方法策略。 微前端架构具备以下几个核心价值&#xff1a; 1、技术栈无关 主框架不限制接入应用的技术栈&#xff0c;微应用具备完全自主权 2、独立开发、独立部署 微应用仓库独立&#xff0…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散

前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说&#xff0c;在叠衣服的过程中&#xff0c;我会带着团队对比各种模型、方法、策略&#xff0c;毕竟针对各个场景始终寻找更优的解决方案&#xff0c;是我个人和我司「七月在线」的职责之一 且个人认为&#xff0c…...

sshd代码修改banner

sshd服务连接之后会收到字符串&#xff1a; SSH-2.0-OpenSSH_9.5 容易被hacker识别此服务为sshd服务。 是否可以通过修改此banner达到让人无法识别此服务的目的呢&#xff1f; 不能。因为这是写的SSH的协议中的。 也就是协议规定了banner必须这么写。 SSH- 开头&#xff0c…...

ubuntu中安装conda的后遗症

缘由: 在编译rk3588的sdk时&#xff0c;遇到编译buildroot失败&#xff0c;提示如下&#xff1a; 提示缺失expect&#xff0c;但是实测相关工具是在的&#xff0c;如下显示&#xff1a; 然后查找借助各个ai工具&#xff0c;重新安装相关的工具&#xff0c;依然无解。 解决&am…...

C++中vector类型的介绍和使用

文章目录 一、vector 类型的简介1.1 基本介绍1.2 常见用法示例1.3 常见成员函数简表 二、vector 数据的插入2.1 push_back() —— 在尾部插入一个元素2.2 emplace_back() —— 在尾部“就地”构造对象2.3 insert() —— 在任意位置插入一个或多个元素2.4 emplace() —— 在任意…...

spring boot使用HttpServletResponse实现sse后端流式输出消息

1.以前只是看过SSE的相关文章&#xff0c;没有具体实践&#xff0c;这次接入AI大模型使用到了流式输出&#xff0c;涉及到给前端流式返回&#xff0c;所以记录一下。 2.resp要设置为text/event-stream resp.setContentType("text/event-stream"); resp.setCharacter…...

基于小程序老人监护管理系统源码数据库文档

摘 要 近年来&#xff0c;随着我国人口老龄化问题日益严重&#xff0c;独居和居住养老机构的的老年人数量越来越多。而随着老年人数量的逐步增长&#xff0c;随之而来的是日益突出的老年人问题&#xff0c;尤其是老年人的健康问题&#xff0c;尤其是老年人产生健康问题后&…...