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;
    }
}
相关文章
|
6月前
|
数据采集 算法 Java
业余爱好者想入门编程,一定远离那些只会说No的家伙,尤其程序员
业余爱好者想入门编程,一定远离那些只会说No的家伙,尤其程序员
63 2
|
6月前
|
人工智能 算法 前端开发
想转行IT,有前途嘛?30个详细理由中会得到你想要的答案
想转行IT,有前途嘛?30个详细理由中会得到你想要的答案
122 0
|
程序员
接受平庸,特别是程序员
接受平庸,特别是程序员
|
存储 程序员 C++
如果当初学习编程时能有人给我这些忠告该多好
Cecily Carver 是多伦多的一位程序媛,和 Jennie Faber 一起创办了一个游戏制作工作室。她喜欢歌剧、舞蹈和弹钢琴。Cecily 在这篇文章分享她在编程道路上的所感所想,给出很多值得思考的编程箴言以及一些思想误区,比如在你学习编程之前思考一下你的目标、编程不是什么神秘的东西、坚持比方法更重要等,可以让我们在编程路上少走一些弯路,从而有更多的时间学习技术让自己变的越来越强大。
226 0
|
小程序 Android开发 容器
为何小程序上线了,他们的内心却留下遗憾?
你的小程序还是那么卡卡卡卡么?
7723 0
为何小程序上线了,他们的内心却留下遗憾?
|
敏捷开发 Java 程序员
说说哪本书是对程序员最有影响、每个程序员都该阅读的书?
网上有很多关于程序员必读的书单,感觉都不是很有代表性。今天无意看到了一篇总结还算不错的书单。和园友们分享。以下书单中提到的书看过一部分,给我的感觉是经典就是经典。读过之后确实得到了很多东西,它们都潜在的影响着我。
981 0
|
数据安全/隐私保护 Python Java

相关实验场景

更多