首页 > 试题广场 >

幸运的袋子

[编程题]幸运的袋子

热度指数：24513 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

一个袋子里面有n个球，每个球上面都有一个号码(拥有相同号码的球是无区别的)。如果一个袋子是幸运的当且仅当所有球的号码的和大于所有球的号码的积。
例如：如果袋子里面的球的号码是{1, 1, 2, 3}，这个袋子就是幸运的，因为1 + 1 + 2 + 3 > 1 * 1 * 2 * 3
你可以适当从袋子里移除一些球(可以移除0个,但是别移除完)，要使移除后的袋子是幸运的。现在让你编程计算一下你可以获得的多少种不同的幸运的袋子。

输入描述:

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

输出描述:

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

示例1

输入

3
1 1 1

输出

算法知识视频讲解

Java

抓住努力的尾巴

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
            int n =scan .nextInt();
            int[] a=new int[n];
            for(int i = 0; i < n; i++) {
                a[i] = scan.nextInt();
            } 
            Arrays.sort(a);
            int num = count(a, n, 0, 0, 1);
            System.out.println(num);

    } 
    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) {
                count = count + count(a, n, i + 1, sum, multi);
            }else{
                break;
            } 
            sum = sum - a[i];
            multi = multi / a[i];
            while(i < n - 1 && a[i] == a[i+1]) {
                i++;
            }
        } 
        return count;
    }
}

发表于 2022-09-28 22:58:39 回复(0)

Java

来学习的小张

import java.util.*;
public class Main{
    public static int cou(int[] arr,int n,int pos,int sum,int mutily){
        int count = 0;
        for(int i = pos;i < n;i++){
            sum = sum + arr[i];
            mutily = mutily * arr[i];
            if(sum > mutily){
                //继续往下递归
                count = count + 1 + cou(arr,n,i + 1,sum,mutily);
            }else if(arr[i] == 1){
                //任何数与一相加 都大于与一相乘
                count = count + cou(arr,n,i + 1,sum,mutily);
            }else{
                break;
            }
            //回溯到上一层
            sum -= arr[i];
            mutily /= arr[i];
            while(i < n - 1 && arr[i] == arr[i + 1]){
                i++;
            }
        }
        return count;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0;i <n;i++){
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        int count = cou(arr,n,0,0,1);
        System.out.println(count);
    }
}

发表于 2022-04-05 15:31:13 回复(0)

Java

jianhanke

// jipackage A_nowcoder;

import java.util.Arrays;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

    static int count=0;
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] data = new int[n];
        for (int i = 0; i <n ; i++) {
            data[i]=scanner.nextInt();
        }
        Arrays.sort(data);
        traceLuck(data,0,0L,1L);
        System.out.println(count);
    }

    public static void traceLuck(int[] data,int index ,Long sum,Long amass){

        if(sum>amass){
  
            ++count;
        }else{
            if(sum!=0 && amass!=1 && index<data.length &&  data[index]>1) {
                return;
            }
        }

        for (int i = index; i <data.length ; i++) {
            
            if(i>index && data[i]==data[i-1])
                continue;
            traceLuck(data,i+1,sum+data[i],amass*data[i]);
        }
        return;


    }

}

发表于 2021-03-03 16:13:55 回复(0)

Java

三生石1103

深度优先搜索加强剪枝

首先计算每个球的数字出现的次数，从小（2开始）到大添加，添加的个数为（0...n）n为这个数字出现的最大次数

剪枝：乘积大于和 + 1 出现的次数


import java.util.Scanner;

/**
 * Created by ZLei on 2018/8/7.
 */
public class Main {

    public static final int NUMBER_ON_BALL = 1001;
    public static int ans = 0;
    public static int ballMax = 0;
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            ans = 0;
            ballMax = 0;
            int ballNum = scanner.nextInt();
            int[] balls = new int[NUMBER_ON_BALL];
            for(int i = 0; i < ballNum; i++){
                int numOnBall = scanner.nextInt();
                balls[numOnBall]++;
                ballMax = Math.max(numOnBall, ballMax);
            }

            dfs(2,balls,1,0);
            System.out.println(ans);
        }
        scanner.close();
    }

    public static void dfs(int index, int balls[], int mul, int add){
        if(mul > add + balls[1]) return;
        if(index == (ballMax+1)){
            ans += balls[1] - (mul - add);
            return;
        }

        for(int j = 0; j <= balls[index]; j++){
            int newMul = mulNum(mul, index,j);
            int newAdd = addNum(add,index,j);
            if(newMul > newAdd + balls[1]) break;
            dfs(index+1, balls,newMul,newAdd );
        }


    }

    public static int addNum(int oldAdd, int addNum, int addTime){
        return oldAdd + addNum * addTime;
    }

    public static int mulNum(int oldMul, int mulNum, int mulTime){
        for(int i = 0; i < mulTime; i++){
            oldMul *= mulNum;
        }
        return oldMul;
    }
}

发表于 2018-08-07 11:51:46 回复(0)

Java

七仔0312

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine().trim());
        String[] strings = br.readLine().split(" ");
        int[] nums = new int[N];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = Integer.parseInt(strings[i]);
        }
        Arrays.sort(nums);
        int result = getCount(nums, 0, 0, 1);
        System.out.println(result);
    }

    /**
     * 获取幸运袋子
     * @param arr 排序好的数组
     * @param start 数组遍历开始序号
     * @param sum 和
     * @param mul 积
     * @return
     */
    public static int getCount(int[] arr, int start, int sum, int mul) {
        int count = 0;
        for (int i = start; i < arr.length; i++) {
            sum += arr[i];
            mul *= arr[i];
            //取数arr[i],如果加入后和大于积，说明符合要求，则迭代添加下一个数
            if (sum > mul) {
                count += 1 + getCount(arr, i+1, sum, mul);
            //由于1的特殊性，如果当前sum不大于mul，且arr[i]为1，可以继续遍历
            } else if (arr[i] == 1) {
                count += getCount(arr, i+1, sum, mul);
            } else
                break;
            //sum和mul复位
            sum -= arr[i];
            mul /= arr[i];
            //找下一个不同的数操作同样的步骤
            while (i < arr.length-1 && arr[i] == arr[i+1]){
                i++;
            }
        }
        return count;
    }
}

发表于 2018-03-15 15:50:24 回复(0)