MIOJ #98 買香蕉 ??

描述

我是一個愛吃香蕉的強迫癥。今天我要去水果店論筐買香蕉。 現(xiàn)在水果店有好多筐香蕉，我的要求是買回來的每一筐里必須有相同數(shù)量的香蕉。 為了實現(xiàn)這個目標，你可以每次做兩件事情。 1）放棄筐里的一部分香蕉 2）連筐帶香蕉放棄一整筐 我想知道我能得到最多多少香蕉。

輸入

以空格分割的多個正整數(shù)，每個正整數(shù)表示一筐香蕉的總香蕉數(shù)

輸出

最多能得到的香蕉數(shù)

輸入樣例

1 2 3
5 0 29 14

輸出樣例

4
29

解法

大力出奇跡，暴力解法

這個問題無非是選擇哪幾筐的問題，先把所有可能的選擇枚舉出來，然后找到每個選擇中最小的那筐，每筐都是這個數(shù)量時就是最終獲得的香蕉數(shù)量，遍歷所有所有選擇然后找到香蕉數(shù)量最大的即可。

第一步：枚舉出所有的方案。集合 {1,2,3}枚舉出所有的方案有
2³ 種，除去空集，還有7個。1~7,幾個數(shù)字換算為二進制分別是，001，010，011，100，101，110，111，每一位的0還是1可以視作是否選擇這個元素。依照這個想法，我們可以寫出程序枚舉出所有的可能方案。

第二步：計算每一種方案對應(yīng)可獲得的香蕉數(shù)量，就是每種方案中香蕉數(shù)量最小值*筐的數(shù)量。

代碼如下：

package  com.li2niu.mioj.day7.BuyBananas; 
 import  java.util.Arrays;  import  java.util.Scanner;  /**
 * @author chuanyi@88.com
 * @date 2020/10/29
 * @Description
 */ 
 public  class  Main  {  public  static  void  main(String[] args)  {  Scanner scan =  new  Scanner(System.in);  String line;  while  (scan.hasNextLine())  { line = scan.nextLine().trim();  String[] strings = line.split(" ");  int[] nums =  new  int[strings.length];  for  (int i =  0; i < strings.length; i++)  { nums[i]  =  Integer.parseInt(strings[i]);  }  System.out.println(buyBananas(nums));  }  }  private  static  int  buyBananas(int[] nums)  {  String[] buyMethods =  enumBuyMethod(nums);  int max =  0;  for  (String buyMethod : buyMethods)  {  String[] numbers = buyMethod.split(",");  int min = nums[Integer.parseInt(numbers[0])];  for  (int i =  1; i < numbers.length; i++)  {  int temp = nums[Integer.parseInt(numbers[i])];  if  (temp < min)  { min = temp;  }  }  int count = min * numbers.length;  if  (count > max)  { max = count;  }  }  return max;  }  /**
     * 枚舉導(dǎo)致內(nèi)存超限,只存下標
     * 使用字符串存儲每一種方案中的筐的下標
     * @param nums
     * @return
     */  private  static  String[]  enumBuyMethod(int[] nums)  {  int length = nums.length;  int subSetNum =  (int)  Math.pow(2, length);  int temp;  String[] strings =  new  String[subSetNum -  1];  for  (int i =  0; i < subSetNum; i++)  {  if  (i ==  0)  {  continue;  } temp = i;  StringBuilder set =  new  StringBuilder();  for  (int j =  0; j < length; j++)  {  if  ((temp &  1)  ==  1)  { set.append(j);  if  (j < length -  1)  { set.append(",");  }  } temp >>=  1;  }  if  (set.charAt(set.length()  -  1)  ==  ',')  { set.deleteCharAt(set.length()  -  1);  } strings[i -  1]  = set.toString();  }  return strings;  }  }  

時間復(fù)雜度為 O(2ⁿ⁺¹n) 。枚舉的總數(shù)為 2ⁿ ，每種方案都需要遍歷數(shù)字的每個二進制位取出對應(yīng)筐的下標，這個長度是 n ，最后統(tǒng)計每一種方案對應(yīng)的香蕉數(shù)也是相同的復(fù)雜度。這樣，時間復(fù)雜度就是O(2ⁿ⁺¹n) 。

空間復(fù)雜度 O(2ⁿ-1)=O(2ⁿ) 。一個用于存儲方案的輔助數(shù)組。

但是這樣的暴力方法會內(nèi)存超限?。?！

排序，找短板

有什么其他的辦法嗎？

題設(shè)說，筐中的香蕉是可以放棄一部分的。 比較容易想到的一點是找到一筐數(shù)量比較少最佳的香蕉，然后讓其他的筐都減少到相同的數(shù)量。因為香蕉只能減少，不能增加，我們應(yīng)當從數(shù)量較少的香蕉筐開始，讓其余的可能的香蕉筐放棄一部分以達到相同的數(shù)量。

第一步：從小到大排列香蕉筐

第二部：從小到大遍歷這些筐，讓比當前筐多的香蕉都保持相同的數(shù)量，求出可以得到的香蕉總數(shù)。找到這些總和的最大值。

代碼如下：

package  com.li2niu.mioj.day7.BuyBananas;  import  java.util.Arrays;  import  java.util.Scanner;  /**
 * @author chuanyi@88.com
 * @date 2020/10/29
 * @Description
 */  public  class  Main  {  public  static  void  main(String[] args)  {  Scanner scan =  new  Scanner(System.in);  String line;  while  (scan.hasNextLine())  { line = scan.nextLine().trim();  String[] strings = line.split(" ");  int[] nums =  new  int[strings.length];  for  (int i =  0; i < strings.length; i++)  { nums[i]  =  Integer.parseInt(strings[i]);  }  System.out.println(buyBananas1(nums));  }  }  private  static  int  buyBananas1(int[] nums)  {  Arrays.sort(nums);  int max =  0;  int length = nums.length;  for  (int i =  0; i < length; i++)  {  int count = nums[i]  *  (length - i);  if  (count > max)  { max = count;  }  }  return max;  }  }  

時間復(fù)雜度是

O(nlogn+n)=O(nlogn) 。使用的Arrays.sort 時間復(fù)雜度是O(nlogn) ,遍歷需要O(n) 。

空間復(fù)雜度O(1) 。