WY15 幸运的袋子

简介: WY15 幸运的袋子

练习题入口

问题描述

  一个袋子里面有n个球,每个球上面都有一个号码(拥有相同号码的球是无区别的)。如果一个袋子是幸运的当且仅当所有球的号码的和大于所有球的号码的积。

例如:如果袋子里面的球的号码是{1, 1, 2, 3},这个袋子就是幸运的,因为1 + 1 + 2 + 3 > 1 * 1 * 2 * 3

   你可以适当从袋子里移除一些球(可以移除0个,但是别移除完),要使移除后的袋子是幸运的。现在让你编程计算一下你可以获得的多少种不同的幸运的袋子。

输入描述:

第一行输入一个正整数n(n ≤ 1000) 第二行为n个数正整数xi(xi ≤ 1000)

输出描述:

输出可以产生的幸运的袋子数

解题分析

  题中要我们找寻 “幸运袋子数”,也就是 ‘一堆数相加’ 大于 ‘一堆数相乘’。如下图,我们能列出许多这样的式子,但是这样太麻烦了也不利于编程,所以我们一般碰到这一类的题就先把数组排序。

第一步:从小到大排序数组

第二步:开始从一个元素查找“幸运袋子”

 我们先定义一个 sum 和一个 multi 分别记录‘一堆数相加’ 大于 ‘一堆数相乘’。同时定义一个 count 记录幸运袋子数。


  首先从a1开始循环查找,a1自己不能组成“幸运袋子”,往后遍历到 a2,因为 a1*a2 > a1+a2,所以 count++,a1和a2达成条件,然后接着遍历到 a3,条件成立,count++。


   下一个到 a4 ,因为a1*a2*a3*a4 < a1+a2+a3+a4,条件不成立,此时a5我们就不用遍历了,肯定不成立,所以直接 break 返回到a3那一层。

a5 > a4 ,当a4不成立时,a5肯定也不成立,这个也就是排序的好处,减少编程难度

 此时回到上一层,现在要从a2到a4,所以我们要让 sum 减去 a3,multi 除去 a3  ,接着往下遍历,直到遍历到不成立的数。

要注意两种特殊情况:

  1. a[i] == 1   1 和任何数的和都大于它和任何数的积  
  2. 拥有相同号码的球是无区别的

这些会在代码中标记处理

代码实现

import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int[] arr = new int[n];
        for(int i = 0;i < n;i++){
            arr[i] = in.nextInt();
        }
        Arrays.sort(arr);
        System.out.println(Count(arr,n,0,0,1));
    }
    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];
            if(sum>multi){
                count=count+1+Count(a,n,i+1,sum,multi);
            }else if(a[i] == 1){
                //特殊情况1 当a[i]==1时可以直接向下递归
                count=count+Count(a,n,i+1,sum,multi);
            }else{
                break;
            }
            sum = sum - a[i];
            multi/=multi/a[i];
            //特殊情况2,当碰见相同数值,我们直接跳过
            while(i<n-1 && a[i]==a[i+1]){
                i++;
            }
        }
        return count;
    }
}
相关文章
|
2月前
|
人工智能
被AI裁掉的35岁设计师,0成本开了家一人公司,月入数万还出海了
35岁品牌设计师被AI裁员后,0成本创办一人公司:用AI独立完成短剧承制,月入数万,作品出海新法。站对杭州上城区政策风口——亿元补贴、算力券、免费工位,实现“作品先行、B端变现、城市赋能”。真正启示:被冲击不可怕,不换工具才可怕。(239字)
|
3月前
|
人工智能 机器人 Java
从 YC 2026 看企业 AI 落地:Agent 标配化之后,真正缺的是部署力
YC 2026 披露近 400 个项目,95% 与 AI 相关、70% 在做 Agent。本文从工程落地角度,分析智能体走向真实世界的三条主线与所需能力,供开发者参考。
341 0
|
3月前
|
人工智能 监控 API
保姆级教程:阿里云百炼平台调用DeepSeek-V4-Pro,免费100万Tokens领取流程
在编程推理、数学演算、复杂长文本任务场景下,DeepSeek-V4-Pro凭借超长上下文窗口、原生思考模式、Function Calling工具调用能力,成为众多开发者首选的旗舰推理模型。很多开发者希望低成本体验该模型完整能力,而阿里云百炼平台提供了直达通道,新用户可申领DeepSeek-V4-Pro专属免费100万Tokens额度,无需复杂本地部署,直接通过兼容API、DashScope SDK完成调用。本文将采用保姆式分步讲解,从账号准备、免费额度自动发放逻辑、业务空间创建、API Key生成、多方式代码调用、思考模式开启、用量监控、常见报错排查完整梳理,让零基础开发者也能顺利完成接入,零
1275 0
|
3月前
|
数据采集 存储 算法
抖音/快手直播选品:用API快速匹配爆款与低价货源
本文介绍面向直播电商的API自动化选品系统,解决人工选品的信息滞后、比价困难、数据割裂与决策主观等痛点。通过对接抖音、快手、1688等平台开放API,构建含数据采集、清洗存储、爆款识别、货源匹配及可视化展示的全链路方案,并提供Python实战代码与优化建议。(239字)
|
4月前
|
人工智能 自然语言处理
AI大模型工具深度运用:企业如何用千问搭建可持续维护的知识库智能体?
企业应用大模型,不能只关注“能否生成”,更要解决“依据什么答”和“谁来负责”。本文系统阐述知识库建设(需核实、去重、分级、结构化)、智能体搭建(六步法)、工作流设计(人机协同)及长效治理机制,强调AI落地核心在于可信知识+明确权责+持续运营。
|
4月前
|
云安全 运维 安全
阿里云国际站:AccessKey泄露风险检测与应急处置指南(云安全中心)
AccessKey 泄露已经成为云上安全事故中响应最急迫的一类——攻击者拿到凭证后,不消半小时就能遍历资源、窃取数据或植入后门。没有一套可落地的阿里云 AccessKey 泄露检测与应急处理指南,多数团队往往在账单爆表或业务中断后才开始被动处置。以下从根因与影响入手,把这条最常见的攻击链拆开来看。
387 0
|
4月前
|
安全 关系型数据库 MySQL
2026阿里云轻量应用服务器38元与云服务器99元解析:配置+适用场景+选购技巧
阿里云目前有两款高人气特惠云服务器:新用户专属轻量应用服务器,2核2G、200M峰值带宽、40G ESSD云盘,不限流量,抢购价仅38元/年,支持WordPress、Docker等精选镜像一键部署,30秒快速启动,集成域名解析、安全防护等一站式运维能力,适配个人博客、学习测试、小型企业官网等场景。同时新老用户同享经济型e实例,2核2G、3M固定带宽,99元/年且续费同价,覆盖全国多地域节点,性能稳定,是中小企业低成本推进数字化转型的高性价比选择。
|
5月前
|
运维 Cloud Native Android开发
安卓苹果云手机别乱买!2026选错直接多花冤枉钱
安卓云手机基于ARM虚拟化,支持ROOT、群控、多开、脚本及虚拟定位,成本低、兼容广、风控强;苹果云手机受限于私有架构,难群控、不兼容安卓应用、价格高30%–50%,仅适合单账号轻度挂机。2026年安卓ARM已成主流。
980 0
|
5月前
|
Oracle 关系型数据库 MySQL
OBCP V4.0 认证培训课程《数据库开发设计与优化》 对应的考试练习题
本资料为OceanBase V4数据库核心考点精讲,涵盖分区表(MySQL/Oracle模式上限、分区键约束、Hash分布)、索引类型(局部/全局区别与默认行为)、索引设计(等值在前范围在后、匹配规则)、序列与自增列(NOORDER vs ORDER)、复制表与外表、Hint/Outline/SPM及统计信息等8大模块,含61道单选、多选、判断题及解析,助力高效备考。
769 5
|
6月前
|
人工智能 JSON 运维
2026 生产级 AI Agent 自动化:零重型框架,彻底解决多步任务不稳定难题
本文提出“文件即状态”轻量架构,用5个文件实现AI Agent多步任务的稳定执行,无需LangGraph等重型框架。支持断点续跑、幂等重试、跨Agent协同,个人开发者7天即可落地生产级自动化。(239字)