MIOJ #98 買香蕉 ??
描述
我是一個(gè)愛(ài)吃香蕉的強(qiáng)迫癥蜀铲。今天我要去水果店論筐買香蕉戈稿。 現(xiàn)在水果店有好多筐香蕉守谓，我的要求是買回來(lái)的每一筐里必須有相同數(shù)量的香蕉紧卒。 為了實(shí)現(xiàn)這個(gè)目標(biāo)昆烁，你可以每次做兩件事情侥加。 1）放棄筐里的一部分香蕉 2）連筐帶香蕉放棄一整筐 我想知道我能得到最多多少香蕉缆娃。
輸入
以空格分割的多個(gè)正整數(shù)媒抠，每個(gè)正整數(shù)表示一筐香蕉的總香蕉數(shù)
輸出
最多能得到的香蕉數(shù)
輸入樣例
1 2 3
5 0 29 14
輸出樣例
4
29
解法
大力出奇跡弟断，暴力解法
這個(gè)問(wèn)題無(wú)非是選擇哪幾筐的問(wèn)題，先把所有可能的選擇枚舉出來(lái)趴生，然后找到每個(gè)選擇中最小的那筐阀趴，每筐都是這個(gè)數(shù)量時(shí)就是最終獲得的香蕉數(shù)量，遍歷所有所有選擇然后找到香蕉數(shù)量最大的即可苍匆。
第一步：枚舉出所有的方案刘急。集合 {1,2,3}枚舉出所有的方案有
23 種，除去空集浸踩，還有7個(gè)叔汁。1~7,幾個(gè)數(shù)字換算為二進(jìn)制分別是，001检碗，010据块，011，100折剃，101另假，110，111怕犁，每一位的0還是1可以視作是否選擇這個(gè)元素边篮。依照這個(gè)想法，我們可以寫(xiě)出程序枚舉出所有的可能方案奏甫。
第二步：計(jì)算每一種方案對(duì)應(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)存超限,只存下標(biāo)
* 使用字符串存儲(chǔ)每一種方案中的筐的下標(biāo)
* @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; } }
時(shí)間復(fù)雜度為 O(2n+1n) 阵子。枚舉的總數(shù)為 2n 思杯，每種方案都需要遍歷數(shù)字的每個(gè)二進(jìn)制位取出對(duì)應(yīng)筐的下標(biāo)，這個(gè)長(zhǎng)度是 n 挠进，最后統(tǒng)計(jì)每一種方案對(duì)應(yīng)的香蕉數(shù)也是相同的復(fù)雜度色乾。這樣腾么，時(shí)間復(fù)雜度就是O(2n+1n) 。
空間復(fù)雜度 O(2n-1)=O(2n) 杈湾。一個(gè)用于存儲(chǔ)方案的輔助數(shù)組解虱。
但是這樣的暴力方法會(huì)內(nèi)存超限！Ｆ嶙病殴泰！
排序，找短板
有什么其他的辦法嗎浮驳？
題設(shè)說(shuō)悍汛，筐中的香蕉是可以放棄一部分的。 比較容易想到的一點(diǎn)是找到一筐數(shù)量比較少最佳的香蕉至会，然后讓其他的筐都減少到相同的數(shù)量离咐。因?yàn)橄憬吨荒軠p少，不能增加奉件，我們應(yīng)當(dāng)從數(shù)量較少的香蕉筐開(kāi)始宵蛀，讓其余的可能的香蕉筐放棄一部分以達(dá)到相同的數(shù)量。
第一步：從小到大排列香蕉筐
第二部：從小到大遍歷這些筐县貌，讓比當(dāng)前筐多的香蕉都保持相同的數(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; } }
時(shí)間復(fù)雜度是
O(nlogn+n)=O(nlogn) 梧宫。使用的Arrays.sort 時(shí)間復(fù)雜度是O(nlogn) ,遍歷需要O(n) 。
空間復(fù)雜度O(1) 摆碉。
