習(xí)題鏈接：幸運(yùn)的袋子_?？皖}霸_?？途W(wǎng)

題目分析

?由題意可知：“幸運(yùn)的袋子”的概念是——小球的數(shù)值之和大于小球的數(shù)值之積。

假如現(xiàn)在有5個(gè)小球：1，1，3，5，7，并將他們編號(hào)a0~a4.我們現(xiàn)在來看其中一種滿足“幸運(yùn)”條件的情況：我們設(shè)置變量sum來記錄數(shù)值之和，用multi來記錄數(shù)值之積，用count來記錄袋子數(shù)量。

?我們先取a0這個(gè)小球，數(shù)值為1。接著取a1——（1+1）>（1*1），滿足條件，計(jì)數(shù)器count+1.我們繼續(xù)取a2——（1+1+3）>（1*1*3），滿足條件，計(jì)數(shù)器count+1.

接著我們?nèi)3，（1+1+3+5+7）<（1*1*3*5*7）,不滿足條件。那么我們就要回到上一層（取a2的那一層）來試試下一個(gè)取a4是否滿足要求。

但是此時(shí)sum = (1+1+3+5+7) = 17，multi = 105,要想回到上一層就得sum減去剛拿到的a3，multi除以剛乘上的a3.然后去取a4，看看是否滿足條件。

但是因?yàn)槲覀儗?duì)數(shù)字進(jìn)行遞增排序了，如果a3不滿足條件，那么a4也不會(huì)滿足。

最后返回count的值。

---

如果我們寫一個(gè)count函數(shù)，用來獲得從取得某個(gè)球開始的“幸運(yùn)袋子”的個(gè)數(shù)。對(duì)于n個(gè)小球來說，自小球a0開始的袋子個(gè)數(shù)為：小球a0與下一個(gè)小球ax之間袋子的個(gè)數(shù) 加上 以小球ax開始與ax的下一個(gè)小球之間的袋子個(gè)數(shù) 之和。然后依次遞歸

那么回到一個(gè)小球也沒取的時(shí)候，此時(shí)為空（什么也沒有），那么袋子的個(gè)數(shù)是不是 取第一個(gè)小球的個(gè)數(shù)（此時(shí)你取哪個(gè)小球都滿足要求，因?yàn)榇藭r(shí)就一個(gè)小球）加上 第一個(gè)小球與其取得下一個(gè)小球所有可能？

很好，現(xiàn)在我們總結(jié)出了其中的規(guī)律，現(xiàn)在我們來寫代碼

---

import java.util.*;
public class FortunatePackage {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();//輸入小球的個(gè)數(shù)int[] a = new int[n];//將所有小球放入一個(gè)數(shù)組中，以數(shù)組下標(biāo)為小球編號(hào)for (int i = 0; i < n; i++) {a[i] = sc.nextInt();}Arrays.sort(a);//將小球遞增排序，以節(jié)省算力/*為什么要排序？仍然以（1，1，3，5，7）為例，當(dāng)取到5時(shí)，5不滿足要求，那么它后面的數(shù)都比它大，也一定不滿足要求了*/System.out.println(count(a, n, 0, 0, 1));//從第一個(gè)下標(biāo)開始取小球}/*pos是查找“幸運(yùn)袋子”時(shí)的“第一個(gè)球的位置”，a[]是目前可供挑選的球，sum為和（初始值為0），multi為積（初始值為1），n為球的個(gè)數(shù)*/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];//如果這兩個(gè)球滿足“幸運(yùn)袋子”的要求，“幸運(yùn)袋子”的組合種類數(shù)為 1（這兩個(gè)球組成的袋子）+ 剩下的所有球中存在的“幸運(yùn)袋子”數(shù)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;}//如果這兩個(gè)球不滿足“幸運(yùn)袋子”的要求，則清除此次操作帶來的數(shù)據(jù)改變，回溯到上一層sum -= a[i];multi /= a[i];//如果這個(gè)球不滿足要求并且和下一個(gè)球的數(shù)值相等，則跳過下一個(gè)球的檢測while (i < n-1 && a[i] == a[i+1]){i++;}}return count;}
}