一个袋子里面有n个球，每个球上面都有一个号码(拥有相同号码的球是无区别的)。如果一个袋子是幸运的当且仅当所有球的号码的和大于所有球的号码的积。
例如：如果袋子里面的球的号码是{1, 1, 2, 3}，这个袋子就是幸运的，因为1 + 1 + 2 + 3 > 1 * 1 * 2 * 3
你可以适当从袋子里移除一些球(可以移除0个,但是别移除完)，要使移除后的袋子是幸运的。现在让你编程计算一下你可以获得的多少种不同的幸运的袋子。
[编程题]幸运的袋子
//求重复元素的子集，在取子集的过程中若已经不符合限制sum>=prod则剪枝
//去重复子集的方法方法：由于有相同数字，排序，每次选择包不包含当前元素时需要满足3个条件
//1.没有前一个位置
//2.前一个位置与当前不相同
//3.前一个位置相同但在子集里
//不包含都可以
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
while(input.hasNext()){
int n = input.nextInt();
int[] a= new int[n];
for(int i=0;i<n;i++)
a[i] = input.nextInt();
Arrays.sort(a);
int ans = subset(0,0,1,a,false);
System.out.println(ans);
}
}
public static int subset(int isofar,int sum,int prod,int[] a,boolean pretaken){
if(isofar==a.length&&sum>prod) return 1;//找到一个子集
else if(isofar==a.length) return 0;
if(sum<prod&&!(sum==0&&prod==1)) return 0;//剪枝，由于是排序过的，如果当前就已经超出限制，往后找肯定也是超出限制
int ans = 0;
if(isofar==0||a[isofar]!=a[isofar-1]||pretaken)//用于去除相同数字的重复单独选取
ans += subset(isofar+1,sum+a[isofar],prod*a[isofar],a,true);
ans += subset(isofar+1,sum,prod,a,false);
System.out.println(isofar+" "+sum+" "+prod+" "+ans);
return ans;
}
}
编辑于 2017-09-09 19:57:19
回复(0)
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
int GetLuckyNum(vector<int>& v,int n,int pos,int sum,int mul)
{
int count = 0;//深度优先遍历
for(int i=pos;i<n;++i)
{
sum += v[i];
mul *= v[i];
if(sum>mul)//说明满足幸运袋子 如 1 1 3 4 5 113满足接下来看1135
{
count += 1 + GetLuckyNum(v, n, i+1, sum, mul);
}
else if(v[i]==1)
{
count += GetLuckyNum(v, n, i+1, sum, mul);
}
else//走到这里说明不满足幸运袋子了 1 1 3 4 如
{
break;//回到上一层
}
sum -= v[i];
mul /= v[i];
while(i<n-1 && v[i]==v[i+1])
{
++i;
}
}
return count;
}
int main()
{
int n;
cin>>n;
vector<int> v(n);
for(int i=0;i<n;++i)
{
cin>>v[i];
}
sort(v.begin(),v.end());
cout<<GetLuckyNum(v,n,0,0,1)<<endl;
return 0;
}
发表于 2021-10-28 21:36:57
回复(0)
#include <iostream>
#include <algorithm>
using namespace std;
/*
getLuckyPacket:从当前位置开始搜索符合要求的组合，一直搜索到最后一个位置结束
x[]: 袋子中的所有球
n: 球的总数
pos: 当前搜索的位置
sum: 到目前位置的累加和
multi: 到目前位置的累积值
*/
int getLuckyPacket(int arr[], int n, int pos, int sum, int multi){
int count = 0;
//循环，搜索以位置i开始所有可能的组合
for(int i = pos; i < n; ++i){
sum += arr[i];
multi *= arr[i];
if(sum > multi){
//找到符合要求的组合，加1，继续累加后续的值，看是否有符合要求的集合
count += 1 + getLuckyPacket(arr, n, i + 1, sum, multi);
}
else if(arr[i] == 1){
//如果不符合要求，且当前元素值为1，则继续向后搜索
count += getLuckyPacket(arr, n, i + 1, sum, multi);
}
else{
//如果sum小于multi,则后面就没有符合要求的组合了
break;
}
//要搜索下一个位置之前，首先恢复sum和multi
sum -= arr[i];
multi /= arr[i];
//数字相同的球，没有什么区别，都只能算一个组合，所以直接跳过
while(i < n - 1 && arr[i] == arr[i + 1]){
++i;
}
}
return count;
}
int main(){
int n;
while(cin >> n){
int arr[n];
for(int i = 0; i < n; ++i){
cin >> arr[i];
}
sort(arr, arr + n); //从第一个位置开始搜索
cout << getLuckyPacket(arr, n, 0, 0, 1) << endl;
}
return 0;
}
编辑于 2020-06-09 16:23:13
回复(0)
方法一：
import java.util.*;
public class Main{
static int count;
public static void main(String[] args){
Scanner input=new Scanner(System.in);
while(input.hasNext()){
int n=input.nextInt();
int[] x=new int[n];
for(int i=0; i<n; i++)
x[i]=input.nextInt();
Arrays.sort(x);
count=0;
isNumbers(x, 0, 0, 1);
System.out.println(count);
}
}
public static void isNumbers(int[] x, int index, int num, int mul){
if(index!=0){
if(num>mul)
count++;
else if(num<mul)
return;
}
for(int i=index; i<x.length; i++){
num+=x[i];
mul*=x[i];
isNumbers(x, i+1, num, mul);
num-=x[i];
mul/=x[i];
while(i<x.length-1 && x[i]==x[i+1])
i++;
}
}
}
————————————————————————————————————————————————————————————————
方法二：
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner input=new Scanner(System.in);
while(input.hasNext()){
int n=input.nextInt();
int[] x=new int[n];
for(int i=0; i<n; i++)
x[i]=input.nextInt();
Arrays.sort(x);
int count=isNumbers(x, 0, 0, 1);
System.out.println(count);
}
}
public static int isNumbers(int[] x, int index, int num, int mul){
int count=0;
for(int i=index; i<x.length; i++){
num+=x[i];
mul*=x[i];
if(num>mul)
count+=1+isNumbers(x, i+1, num, mul);
else if(x[i]==1)
count+=isNumbers(x, i+1, num, mul);
else
break;
num-=x[i];
mul/=x[i];
while(i<x.length-1 && x[i]==x[i+1])
i++;
}
return count;
}
}
编辑于 2018-05-25 10:43:21
回复(0)
#include <iostream>
#include <algorithm>
using namespace std;
int n,a[1007];
int DFS(int step, int sum, int mul)
{ int r = 0; for(int i=step+1;i<n;i++) { int S = sum+a[i]; int M = mul*a[i]; if(S > M) r += 1 + DFS(i,S,M); else if(a[i]==1) r += DFS(i,S,M); else break; while(i<n-1 && a[i]==a[i+1]) i++; } return r;
}
int main()
{ cin>>n; for(int i=0;i<n;i++) cin>>a[i]; sort(a,a+n); cout<<DFS(0,1,1)<<endl; return 0;
}
发表于 2018-01-24 23:13:50
回复(0)
对 @小刀初试 的代码的稍加修改，感觉更符合我自己对深度优先搜索的理解思路
###修改版本1
def DFS(Tuple,Start,Sum,Product):
ret=0;
for i in range(Start,len(Tuple)):
if(i>Start and Tuple[i][1]==Tuple[i-1][1]):
continue;
curSum=Sum+Tuple[i][1];
curProduct=Product*Tuple[i][1];
if(curSum>curProduct):
ret=ret+1+DFS(Tuple,i+1,curSum,curProduct);
elif(Tuple[i][1]==1):
ret=ret+DFS(Tuple,i+1,curSum,curProduct);
else:
break;
return ret;
###修改版本2
def DFS_1(Tuple,root,Sum,Product):
ret=0;
firstChild_index=root+1;
for i in range(firstChild_index,len(Tuple)):
if(i>firstChild_index and Tuple[i][1]==Tuple[i-1][1]):
continue; ###根节点的第二个孩子节点开始，如果它跟它的前一个节点值相同就跳过。避免重复序列的出现
curSum=Sum+Tuple[i][1];
curProduct=Product*Tuple[i][1];
if(curSum>curProduct):
ret=ret+1+DFS_1(Tuple,i,curSum,curProduct);
else:
break;
return ret;
def main():
n=int(raw_input());
rawList=map(int,raw_input().split());
if(n<=0 ):
print 0;
exit();
rawTuple=[(ind,num) for ind,num in zip(range(n),rawList)];
tuple_sorted=sorted(rawTuple,key=lambda x:x[1]);
###call DFS
print DFS(tuple_sorted,0,0,1);
###call DFS_1
if(tuple_sorted[0][1]!=1): ###符合要求的序列，第一个数字必须是1.
print 0;
exit();
print DFS_1(tuple_sorted,0,1,1); ###就以第一个1为根节点进行深度优先遍历
main();
编辑于 2016-09-02 13:10:55
回复(0)
题目可以转化成求符合条件的集合真子集个数。每次从全集中选择若干元素（小球）组成子集（袋子）。集合子集个数为2^n个，使用dfs必然超时。且此题有重复元素，那么就搜索剪枝。
对于任意两个正整数a,b如果满足 a+b>a*b，则必有一个数为1.可用数论证明：
设a=1+x,b=1+y，则1+x+1+y>(1+x)*(1+y)，--->
1>x*y，则x，y必有一个为0，即a,b有一个为1.
推广到任意k个正整数，假设a1,a2,...ak，如果不满足给定条件，即和sum小于等于积pi，
如果此时再选择一个数b,能使其满足sum+b > pi*b，则，b必然为1，且为必要非充分条件。
反之，如果选择的b>1，则sum+b
<=pi*b，即a1,a2,...,ak,b不满足给定条件。（搜索剪枝的重要依据）
因此，将球按标号升序排序。每次从小到***择，当选择到a1,a2,...,ak-1时满足给定条件，而再增加选择ak时不满足条件（ak必然大于等于max(a1,a2,...,ak-1)），继续向后选择更大的数，必然无法满足！因此，可以进行剪枝。
如果有多个1，即当k=1时，sum(1)>pi(1)不满足，但下一个元素仍为1，则可以满足1+1>1*1，所以要判断当前ak是否等于1.
此外，对于重复数字，要去重复。
#include <stdio.h>
#include <stdlib.h>
int bag[1001],n;
int comp(const void *a,const void *b){
return *(int*)a - *(int*)b;
}
int dfs(int pos,long long sum,long long pi){
int i,c;
for(i=pos,c=0;i<n;++i){
sum+=bag[i];
pi*=bag[i];
if (sum>pi) c+=1+dfs(i+1,sum,pi);
else if (bag[i]==1) c+=dfs(i+1,sum,pi);
else break;
sum-=bag[i];
pi/=bag[i];
for(;i<n-1 && bag[i]==bag[i+1];++i);// duplicate
}
return c;
}
int main(){
int i;
while(~scanf("%d",&n)){
for(i=0;i<n;scanf("%d",&bag[i++]));
qsort(bag,n,sizeof(int),comp);
printf("%d\n",dfs(0,0,1));
}
return 0;
}
编辑于 2016-08-12 14:42:25
回复(20)
#include <iostream>
#include <stdlib.h>
using namespace std;
int n;
int nums[1000];
int cmp(const void * a, const void * b) {
return *(int*)a - *(int*)b;
}
// 思路：DFS生成全组合，同时注意剪枝、避免重复组合
int findall(int nums[], int index, long sum, long multi) {
int count = 0;
for(int i=index; i<n; i++) {
sum += nums[i];
multi *= nums[i];
if(sum > multi)
count += 1 + findall(nums, i+1, sum, multi);
else if(nums[i] == 1)
count += findall(nums, i+1, sum, multi);
else
break;
sum -= nums[i];
multi /= nums[i];
// 跳过相等的元素，避免重复组合
while(i<n-1 && nums[i]==nums[i+1])
i++;
}
return count;
}
int main(int argc, char* argv[])
{
while(cin >> n) {
for(int i=0; i<n; i++)
cin >> nums[i];
// 从小到大排序
qsort(nums, n, sizeof(int), cmp);
cout << findall(nums, 0, 0, 1) << endl;
}
return 0;
}
上述代码已AC。
但是我有一个问题，如果谁知道，请回答一下，谢谢：就是处理输入时总是出现各种问题。。。上述用C++的cin和cout没问题，但是C的scanf和printf就不行(提示超时，实际没超时)，换成Java也总是出现数组越界错误。。。不知道咋回事。。。(未通过的)Java代码如下：
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNextInt()) {
int n = scanner.nextInt();
int[] nums = new int[n];
for(int i=0; i<n; i++)
nums[i] = scanner.nextInt();
Arrays.sort(nums);
System.out.println(find(nums, 0, 0, 1));
}
}
private static int find(int[] nums, int index, long sum, long multi) {
int count = 0;
for(int i=index; i<nums.length; i++) {
sum += nums[i];
multi *= nums[i];
if(sum > multi)
count += 1 + find(nums, i+1, sum, multi);
else if(nums[i] == 1)
count += find(nums, i+1, sum, multi);
else
break;
sum -= nums[i];
multi /= nums[i];
while (i<nums.length-1 && nums[i]==nums[i+1])
i++;
}
return count;
}
}
=============================================
更新：现在Java程序能AC通过了！原因是测试用例多了一个“}”，导致转换为Int失败，向牛客反馈之后，牛客迅速修复了测试用例，ok了。
编辑于 2016-08-10 12:45:33
回复(20)
// 非计算机专业出身，看到评论区的 bfs、修裁树啥的就蒙了。自己用一种纯数学的方法AC，
// 敢兴趣的题友可以看看。
// 解题思路：
// 由常识得知，要让和大于积，主要影响因素是看数组中 1 的个数。因此，我们不妨设数组为
// 如下数组：1 1 1 2 2 2 3 4。我们根据 1 的个数进行分类讨论，讨论如下
// 1.当有 0 个 1 时：此时必无解，你可以随意距离，能找出来算我输……
// 2.当有 1 个 1 时：此时，两位数必是最优解。如 1 2、1 3、1 4。两个数时只有 1 2 2 是最优
// 解；
// 3.当有 2 个 1 时：此时 1 个 1 的情况必为此种情况的子集，即最少有 4 个，然后可以扩充位
// 置，加一位，1 1 2 2 2，此时不是最优解，回到上一位，替换最后一位，1 1 2 3，是，此为
// 增，1 1 2 4，不是，回溯上一位，此时回到 1 个 1 的状态，即 1 （1 3）。结束
// ... ...
// 综上可发现，只要对不同 1 个数进行求最优解即可。以上例为例，将上述规律程序化，如下
// 1 个 1 时——首先看 1 2，符合题意，扩展一位 1 2 2，符合题意，扩展一位 1 2 2 2，不符，
// 回溯至上一位，1 2 2，最后一位变数，1 2 3，不符合题意，回溯至上一位， 1 2，最后一位
// 换数，1 3，符合题意，由于无法扩展，最后一位换数，1 4，符合题意，再次换数。数无，
// 结束。此时个数为 4；
// 2 个 1 时——首先看 1 1 2 符合题意，扩展一位 1 1 2 2 符合题意，1 1 2 2 2 不符合，回溯
// 至上一位并换数 1 1 2 3，符合，继续换数 1 1 2 4不符合，回溯，1 1 3……
// 得到结果 16。你们会发现少了 2 个。这是因为此方法没有计算全是 1 的情况。当数组中只
// 有 1 时，1 的个数 - 1即使最优解。相加即可。
// 需要注意的是当回溯后变数时不要将数组下一位直接补上，因为牵扯到重复问题，我在这里
// 是做了一个小循环以跳过重复数字。方法类似暴力破解，但是由于解得目标最大位数和最大
// 和后后面的不再计算，类似折半，因此速度比暴力破解快。时间复杂度没有计算，实际耗时
// 18 ms。代码如下
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int cont = 0;
void ContOne(int, vector<int>, int, int, int); //（1的个数，非1数，当前位数, 和, 积）
int main(void)
{
int n, numb, OneCont(0); //OneCont用来记录1的总个数
vector<int> list;
cin >> n;
while (n--)
{
cin >> numb;
if (numb > 1)
list.push_back(numb);
else
OneCont++;
}
cont = OneCont - 1; //将纯1数组先计算出来
if (!list.empty())
{
sort(list.begin(), list.end()); //对数组排序
for (int i = 1; i <= OneCont; i++) ContOne(i, list, 0, i, 1);
}
cout << cont << endl;
return 0;
}
void ContOne(int OneNub, vector<int> list, int nowBit, int sum, int mult)
{
for (int i = nowBit; i < list.size(); i++) //迭代计算和与积
{
sum += list[i], mult *= list[i];
if (sum <= mult) //如果不符合，回溯至上一位
break;
else
cont++;
ContOne(OneNub, list, i + 1, sum, mult);
sum -= list[i], mult /= list[i]; //回到上一位后需要恢复数值
while (i < list.size() - 1 && list[i] == list[i + 1])
i++; //寻找不重复
}
}
发表于 2018-02-12 20:29:53
回复(3)
排序+dfs+简单剪枝
#include <cstdio>
#include <cstring>
#include <algorithm>
int x[1002], n;
long long ans;
long long sum, mul;
void dfs(int index)
{
for (int i = index; i<n; i++)
{
sum += x[i];
mul *= x[i];
if (sum>mul)
{
ans++;
dfs(i + 1);
}
else if (x[i] == 1)
{
dfs(i + 1);
}
else
{
sum -= x[i];
mul /= x[i];
break;
}
sum -= x[i];
mul /= x[i];
for (; i < n - 1 && x[i] == x[i + 1]; i++);
}
}
int main()
{
//freopen("1.in", "r", stdin);
while (scanf("%d", &n) != EOF)
{
ans = 0;
sum = 0;
mul = 1;
for (int i = 0; i<n; i++)
scanf("%d", x + i);
std::sort(x, x + n);
dfs(0);
printf("%d\n", ans);
}
return 0;
}
发表于 2017-08-08 12:05:30
回复(6)
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,a[1005];
int dfs(int step,int sum,int mul){
int i,j,res=0;
for(i=step+1;i<n;i++){
int nSum=sum+a[i],nMul=mul*a[i];
if(nSum>nMul) res+=1+dfs(i,nSum,nMul);
else if(a[i]==1) res+=dfs(i,nSum,nMul);
else break;
while(i<n-1&&a[i]==a[i+1]) i++;
}
return res;
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",a+i);
sort(a,a+n);
printf("%d\n",dfs(0,1,1));
}
发表于 2017-10-21 16:12:55
回复(0)
package Wangyi2017Neitui;
import java.util.Arrays;
import java.util.Scanner;
import java.util.concurrent.CountDownLatch;
public class test2 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while(scanner.hasNext()){
int n = scanner.nextInt();
int[] a = new int[n];
for(int i = 0;i < n;i++){
a[i] = scanner.nextInt();
}
Arrays.sort(a); //a升序排列
System.out.println(find(a, 0, 0, 1));
}
}
private static int find(int[] a,int index,long sum,long multi){
int count = 0;
for(int i = index;i < a.length;i++){
sum += a[i];
multi *= a[i];
if(sum > multi){
count = count + 1 + find(a, i+1, sum, multi);
}
else if (a[i] == 1) {
//处理待判断的序列第一个数为1的时候，
//那个1虽然不满足和大于积，但是要保留，继续往下考虑
count = count + find(a, i+1, sum, multi);
}
else {
break;
}
sum -= a[i]; //sum和multi在下一循环中还会用到
multi /= a[i];
for(;i < a.length-1 && a[i] == a[i+1];i++){
// i++; //拥有相同号码的球是无区别的，因此跳过
}
}
return count;
}
}
发表于 2017-12-09 21:47:13
回复(0)
#-*- coding: utf8 -*-
"""
为什么要进行排序呢?
因为和的增长幅度小于积的增长幅度，
当我们发现将该元素添加到袋子里，总和小于总积，那么如果从小到大排列了，该元素后面的元素将都不满足条件.
为什么1要特殊处理呢?
数字1能提高总和值但不会提高总积值，1的个数越多，和更有可能大于积.
"""
n=input()
x=sorted(map(int,raw_input().strip().split(' ')))
def get_count(array,sumv=0, multiv=1):
count=0
for i in xrange(len(array)):
if i>0 and array[i]==array[i-1]:#跳过相同的号码
continue
sumv+=array[i]
multiv*=array[i]
if sumv>multiv:#array[i]可以选择移除或不移除,故count+1
count+=1+get_count(array[i+1:], sumv, multiv)
elif array[i]==1:#array[i]不移除,1可以提高sumv值,保持multiv不变
count+=get_count(array[i+1:], sumv, multiv)
else:
break
#回溯
sumv-=array[i]
multiv/=array[i]
return count
print get_count(x)
发表于 2018-08-01 16:29:15
回复(0)
非递归解法
#include<iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> number(n);
for(int i=0; i<n; i++) {
cin >> number[i];
}
sort(number.begin(), number.end());
int ones = 0;
while(ones<n and number[ones]==1) {
++ones; // 计算1的个数
}
if(ones<=0) { //无1则无解
cout << 0 << endl;
return 0;
}
vector<int> prod = {1}; //记录可行的乘积
vector<int> sum = {0}; //及和
int pre = 0;
for(int i=ones; i<n; ++i) {
int m = sum.size();
int k = 0;
if (number[i] == number[i-1]) {
//如果与前一数一样就没必要重复添加到前面的袋子
k = pre;
}
for( ; k<m; ++k) {
//加入number[i]到各袋子后，是否是幸运的（比负的1的数量多就行）
if(sum[k]+number[i] - prod[k]*number[i] > -ones) {
prod.push_back(prod[k]*number[i]);//保存当前袋子乘积及和
sum.push_back(sum[k]+number[i]);
}
}
pre = m;
}
int count = ones>2? ones-1: 0;//只有1组成的幸运袋子数
for(int k=1; k<sum.size(); ++k) {//通过加入不同数量的1以使各袋子幸运
count += ones + sum[k]-prod[k];
}
cout << count << endl;
return 0;
}
发表于 2018-08-18 16:58:28
回复(0)
上面的思路，简而言之就是，如果sum < mul，并且接下来的数字a大于1，那就没必要继续下去了，因为肯定有sum+a < mul * a，但是如果a为1，那还是有可能sum +1 > mul的，因为上面说了，在sum <pi的情况下，如果存在b使得sum + b > mul * b，那么b一定为1（这是必要不充分条件，不能因此反过来判断“如果b为1则sum+b 一定大于 mul * b”），同时，对于重复的数字也要进行去重（比如数列1 1 1 2 2 3 4，1 1 1 2是满足条件的其中一个幸运袋子，如果不去重，就会出现两个1 1 1 2，导致重复计数）
还有一点就是这道题的代码中去重的方法非常巧妙，用了一个nxt数组来记录非重复的元素的下一个元素的脚标，详见代码：
public class Xingyundedaizi {
public static void main(String[] args) {
// TODO Auto-generated method stub
Xingyundedaizi.cal();
}
public static int[] num;
public static int[] nxt;
public static int N;
public static void cal(){
Scanner in = new Scanner(System.in);
N = in.nextInt();
num = new int[N];
nxt = new int[N];
for(int i = 0; i < N; i++){
num[i] = in.nextInt();
}
Arrays.sort(num);
int p = N;
for(int i = N-1; i >=0; i--){
if(i < N-1 && num[i+1] > num[i]) p = i+1;
nxt[i] = p;
}
System.out.println(dfs(0,0,1));
}
public static int dfs(int st, int sum, int mul){
if(st >= N) return (sum > mul)?1:0;
if(num[st] > 1 && sum < mul) return 0;
return dfs(st+1, sum + num[st], mul*num[st]) + dfs(nxt[st], sum, mul);
}
}
发表于 2017-09-18 12:00:17
回复(0)
#include<iostream>
#include<algorithm>
using namespace std;
int getLuckPacket(int x[], int n, int pos, int sum, int multi) {
int count = 0;
//循环，搜索以位置i开始的所有可能组合
for (int i = pos; i < n; ++i) {
sum += x[i];
multi *= x[i];
if (sum > multi) {
//找到以i位置开始的所有组合的可能
count += 1 + getLuckPacket(x,n, i + 1, sum, multi);
}
else if (x[i] == 1) {
//如果不符合要求，且当前元素为 1
//这里可能会有疑惑，既然不满足为何不直接break,而是继续
//因为加 1 之后可能会导致条件继续成立
//例如 1 1 2 5 1 如果这个下一个为 1，则加 1之后条件成立
count += getLuckPacket(x,n, i + 1, sum, multi);
}
else {
//因为已经对数组进行升序，所以如果下一位不是1 ，那么条件永远不可能满足
//直接退出
break;
}
//要搜索下一个位置之前，先恢复 sum 和 multi
sum -= x[i];
multi /= x[i];
//数字相同的球没有任何区别，都只能算一个组合，所以直接跳过
while (i < n - 1 && x[i] == x[i + 1]) {
i++;
}
}
return count;
}
int main() {
int n;
while (cin >> n) {
int x[n];
for (int i = 0; i < n; ++i) {
cin >> x[i];
}
sort(x, x + n);
//从第一个位置开始搜索
cout << getLuckPacket(x, n, 0, 0, 1) << endl;
}
return 0;
}
#include<algorithm>
using namespace std;
int getLuckPacket(int x[], int n, int pos, int sum, int multi) {
int count = 0;
//循环，搜索以位置i开始的所有可能组合
for (int i = pos; i < n; ++i) {
sum += x[i];
multi *= x[i];
if (sum > multi) {
//找到以i位置开始的所有组合的可能
count += 1 + getLuckPacket(x,n, i + 1, sum, multi);
}
else if (x[i] == 1) {
//如果不符合要求，且当前元素为 1
//这里可能会有疑惑，既然不满足为何不直接break,而是继续
//因为加 1 之后可能会导致条件继续成立
//例如 1 1 2 5 1 如果这个下一个为 1，则加 1之后条件成立
count += getLuckPacket(x,n, i + 1, sum, multi);
}
else {
//因为已经对数组进行升序，所以如果下一位不是1 ，那么条件永远不可能满足
//直接退出
break;
}
//要搜索下一个位置之前，先恢复 sum 和 multi
sum -= x[i];
multi /= x[i];
//数字相同的球没有任何区别，都只能算一个组合，所以直接跳过
while (i < n - 1 && x[i] == x[i + 1]) {
i++;
}
}
return count;
}
int main() {
int n;
while (cin >> n) {
int x[n];
for (int i = 0; i < n; ++i) {
cin >> x[i];
}
sort(x, x + n);
//从第一个位置开始搜索
cout << getLuckPacket(x, n, 0, 0, 1) << endl;
}
return 0;
}
https://blog.csdn.net/qq_43692920
发表于 2019-06-05 22:48:51
回复(0)
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt(); //球的数量
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = scan.nextInt();
}
//排序一下所有球的号码
Arrays.sort(arr);
// 输出
int count1 = sumCount(arr,0,n,0,1);
System.out.println(count1);
}
//首先我们要返回的是幸运袋子的个数 , 而且我们要写一个变量记录和 一个变量记录积 从数组下标0开始遍历
//每遍历一个加一个 和乘 必须得两个球 以上
//product 积 sum 和 index 起始位置
public static int sumCount(int[] arr,int index,int n,int sum,int product) {
//要定义一个变量 记录幸运袋子的数量
int count = 0;
for (int i = index; i < n; i++) {
sum = sum + arr[i];
product = product * arr[i];
//假设满足是幸运袋子
if (sum > product) {
count = count + 1 + sumCount(arr,i+1,n,sum,product); //继续递归往下加
//到这里 就有一种特殊情况 就是 假如第一位是1 a[i] == 1 他的和与积是相同的 要保留 继续往下递归
//因为 1和任何数的和都大于和任何数的积
} else if (arr[i] == 1) {
count = count +sumCount(arr,i+1,n,sum,product);
}else {
break;
}
//返回上一层 继续递归
sum = sum -arr[i];
product = product / arr[i];
//相同省略 回到上一个的时候
while(i < n - 1 && arr[i] == arr[i+1]) {
i++; // 跳过 一样了
}
}
return count;
}
}
编辑于 2024-02-28 22:35:47
回复(0)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int getluckypacket(vector<int> x,int n,int pos,int sum,int multi)
{
int count=0;
for(int i=pos;i<n;i++)
{
sum+=x[i];
multi*=x[i];
if(sum>multi)
count+=1+getluckypacket(x,n,i+1,sum,multi);
else if(x[i]==1)
count+=getluckypacket(x,n,i+1,sum,multi);
else
break;
sum-=x[i];
multi/=x[i];
while(i<n-1&&x[i]==x[i+1])
i++;
}
return count;
}
int main()
{
int n;
while (cin >> n)
{
vector<int> x(n);
for(int i=0;i<n;i++)
{
cin>>x[i];
}
sort(x.begin(),x.end());
cout<<getluckypacket(x,n,0,0,1)<<endl;
}
return 0;
}
发表于 2022-10-30 21:28:55
回复(0)
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)
问题信息
通过挑战的用户
查看代码-
2023-02-21 18:15:16
-
2022-12-31 13:21:45
-
2022-12-21 23:04:04
-
2022-11-06 17:44:50 -
2022-11-05 08:54:17
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
