本文主要是介绍牛客WY15 幸运的袋子 C++实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
幸运的袋子
袋子里的数字和大于数字积，才会是一个幸运的袋子。从这句话中，我们可以得到一个消息，也就是袋子里的数字必须要有1（因为是袋子里全是正整数）。
由这个条件，我们很容易想到先进行排序，再来看袋子是否幸运。
那么我们是要排升序还是降序呢？
升序是一个个的加且乘过去，幸运就+1，直到不幸运就返回重新来，将前面的第一个1删除掉，从第二位位置继续往后面算。
降序除非数据全是1，否则第一次就不幸运。那么你得全部遍历完才能算出结果。
因此我们选择升序会好处理很多。
那么我们可以先写出如下代码，后续再处理幸运的问题。
int main() {int n = 0;cin>> n;vector<int> v;v.reserve(n);for(int i=0;i<n;i++){int j = 0;cin>>j;v.push_back(j);}sort(v.begin(), v.end());}处理幸运，我们应该得想到回溯
第一次计算，我们很容易算到上面这个数据。
当 1 1 2 2 3 不在幸运后，我们就需要回退了，直接break跳出该次递归。
回到1 1 2 2 的位置，因为数据是有序的，后面不可能再次出现幸运了，我们应该去掉最后一个。就变成了1 1 2的情况了。
位置在第二个2的情况我们已经计算过了，那我们现在要走到3。
数据为 1 1 2 3。再来判断是否幸运，一直重复上述步骤。
有了思路，我们开始写代码。
想想参数需要什么，vector里的内容是必须的，还需要pos，代表当前走到的位置，当前袋子之和，还有袋子之积也是不可获取的。那么我们可以定义如下函数
int luckybag(const vector<int>& v, int pos, int sum, int mul)进行循环遍历，计算当前位置（pos）的sum和mul。
如果sum>mul，就先加1在去递归。
不幸运 如果v[i]==1,这个是数据只有一个 1 的情况，也是去递归。不用+1，因为不满足幸运
现在还不幸运，就直接break，数据返回进行回溯。
将当前算的sum和mul减掉（当前的数据已经计算完毕，再往后面添加数据已经不满足幸运条件了，因此要把尾部数据删除掉，再去计算后面数据是否幸运）
最后由于相同号码的球是无区别的，因此需要去重，通过while循环防止重复问题。
int luckybag(const vector<int>& v, int pos, int sum, int mul)
{int count = 0;for (int i = pos; i < v.size(); i++){sum += v[i];mul *= v[i];//只有数据有1的时候才可能sum>mulif (sum > mul)count += 1 + luckybag(v, pos + 1, sum, mul);else if (v[i] == 1)//如果不幸运，并且当前值为1(数据只有1才会这样)count += luckybag(v, pos + 1, sum, mul);elsebreak;sum -= v[i];mul /= v[i];//处理重复问题while (i < v.size() - 1 && v[i] == v[i + 1]){i++;}}return count;
}总代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int luckybag(const vector<int>& v, int pos, int sum, int mul)
{int count = 0;for (int i = pos; i < v.size(); i++){sum += v[i];mul *= v[i];//只有数据有1的时候才可能sum>mulif (sum > mul)count += 1 + luckybag(v, pos + 1, sum, mul);else if (v[i] == 1)//如果不幸运，并且当前值为1(数据只有1才会这样)count += luckybag(v, pos + 1, sum, mul);elsebreak;sum -= v[i];mul /= v[i];//处理重复问题while (i < v.size() - 1 && v[i] == v[i + 1]){i++;}}return count;
}
int main() {int n = 0;cin>> n;vector<int> v;v.reserve(n);for(int i=0;i<n;i++){int j = 0;cin>>j;v.push_back(j);}sort(v.begin(), v.end());cout<<luckybag(v,0,0,1);
}这种回溯题还是很难的，需要多多训练，如果实在难以理解，可以将代码复制到本地编译器中，进行调试，（还可以加上画递归展开图）一步一步看结果。
这篇关于牛客WY15 幸运的袋子 C++实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
