首页 > 试题广场 >

幸运的袋子

[编程题]幸运的袋子

热度指数：24620 时间限制：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

输出

算法知识视频讲解

一条余弦Cos

发表于 2020-12-09 11:55:54

#include<iostream> #include<vector> #include<algorithm> using namespace std; vector <int> arr; //全局变量 int bag(int pos,int su 展开全文

阿贝尔的日记

发表于 2022-09-27 21:06:11

幸运的袋子幸运的袋子 /* 2022-09-27 17:20:37 利用好回溯要想sum > muliti 必须得有一个数为1，不满足幸运口袋时，当前数可能是1，可能后面还有满足幸运口袋的情况直接count += 递归后面的 1 1 3 5 7 1 --》 1 1 --》 1 1 3 展开全文

完全没头绪

发表于 2023-04-01 11:51:43

using System; using System.Collections; using System.Collections.Generic; using System.Linq; public class Program { public static void Main() { 展开全文

硌手的小虫子

发表于 2023-04-08 22:04:10

import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner sc=new Sca 展开全文

来个offer吧求求求了

发表于 2023-04-04 12:23:43

import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc. 展开全文

郑州大学

发表于 2023-04-07 23:26:42

import java.util.*; /** * 解题步骤如下： * 1. 将原号码从小到大排序 * 2. 从第一个号码开始穷举，其中穷举的终止条件是当前号码与前面的号码无法组成幸运的袋子，且当前号码不为 1 * 此时就直接返回即可，因为数组已经是排好序的，后面的数字只会越来越大。展开全文

有趣的迪恩在看牛客

发表于 2023-09-08 12:14:48

// 对存放球中的号码数组进行排序 // 如果前面的号码和<积, 后面的就不用计算都小于； // 如果不满足条件，进行数组回溯，判断当前号码前面的号码与当前号码后面的和，积进行判断判断 // 考虑特殊情况arr[i] == 1; import java.util.*; public clas 展开全文