小学网站模板免费下载,做微信网站公司名称,顺德电子画册网站建设,建立一个虚拟公司的网站题目分析 一个袋子里面有n个球#xff0c;每个球上面都有一个号码(拥有相同号码的球是无区别的)。如果一个袋子是幸运的当且仅当所有球的号码的和大于所有球的号码的积。 例如#xff1a;如果袋子里面的球的号码是{1, 1, 2, 3}#xff0c;这个袋子就是幸运的#xff0c;因为…题目分析 一个袋子里面有n个球每个球上面都有一个号码(拥有相同号码的球是无区别的)。如果一个袋子是幸运的当且仅当所有球的号码的和大于所有球的号码的积。 例如如果袋子里面的球的号码是{1, 1, 2, 3}这个袋子就是幸运的因为1 1 2 3 1 * 1 * 2 * 3 你可以适当从袋子里移除一些球(可以移除0个,但是别移除完)要使移除后的袋子是幸运的。现在让你编程计算一下你可以获得的多少种不同的幸运的袋子。
解题思路 这道题的本质是在集合中找出符合条件的子集。 对于两个任意正整数ab来说如果abab则必须有一个数为1可以用数论来证明这里不再赘述。 推广到任意k个正整数假设a1,a2,…ak如果不满足条件即summulti如果再选一个数使sumb multib这个b一定是1相反如果选择的b1则sumb multi*b那么a1,a2,…ak,b就不满足给定的条件。 所以要将这些球进行升序排序。每次从小到大选择当选择到a1,a2,…ak-1时满足给定条件再增加ak是不满足条件那么ak必然要大于等于之前的最大值如果继续向后选择更大的数必然无法满足给定条件。 如果有多个1并且k1使不满足条件但是下一个元素仍为1就可以满足条件所以当位置吐过是1虽然不满足条件但是应该继续向后搜索因为仍然有可能满足条件。 对于重复的数字组合只能算一个所以要跳过这个数字也就是去重
代码实现必要的地方有注释
#include iostream
#include algorithm
#include vectorusing namespace std;int getLuckBox(vectorint x, size_t n, size_t pos, int sum, int multi)
{int count 0;for (size_t i pos; i n; i){sum x[i];multi * x[i];if (sum multi){//如果当前位置可以满足要求就继续从下一个位置开始count 1 getLuckBox(x, n, i 1, sum, multi);}else if (x[i] 1){//如果这个位置是1并且不满足可以从下一个位置尝试count getLuckBox(x, n, i 1, sum, multi);}else{//如果当前位置不满足那么之后更大的数字也不可能满足直接直接返回不再查找break;}//在搜索下一个位置前要先恢复sum和multisum - x[i];multi / x[i];//如果喝下一个位置一样就直接跳过不能有重复while (i n - 1 x[i] x[i 1]){i;}}return count;
}int main()
{size_t n;while (cin n){vectorint x;for (size_t i 0; i n; i){int tmp;cin tmp;x.push_back(tmp);}//按升序排序sort(x.begin(), x.end());cout getLuckBox(x, n, 0, 0, 1);}return 0;
}
