ETH官方钱包

前往
大廳
主題

[leetcode]1889. Minimum Space Wasted From Packaging

???\~O_O~/??? | 2021-08-31 12:00:05 | 巴幣 2 | 人氣 353

題目: 1889. Minimum Space Wasted From Packaging
難度: Hard
目前下列解法的時(shí)間複雜度: O( |包裹|*lg(|包裹|) + |所有箱子|*lg(max(|所有箱子|,|包裹|)) )


題目說明

給定一堆包裹及一堆箱子供應(yīng)商。每個(gè)包裹有一個(gè)大小;每個(gè)箱子有一個(gè)容量。
選擇一個(gè)箱子供應(yīng)商(供應(yīng)多種箱子,每種箱子無限供應(yīng)),每個(gè)包裹使用一個(gè)箱子裝箱,用此供應(yīng)商的箱子裝完所有包裹,計(jì)算最少空間浪費(fèi)(=箱子容量-包裹大小)總和。
問所有箱子供應(yīng)商中,可以達(dá)成的最小浪費(fèi)為何。若沒有任何一個(gè)箱子供應(yīng)商可以提供夠大的箱子裝下最大的包裹,則回傳 -1 。


解法: just do it

1. 把包裹排序,並建立包裹 prefix sum 。
2. 分別對每個(gè)箱子供應(yīng)商的箱子排序
3. 從小箱子到大箱子,每個(gè)箱子花 O(lg(|包裹|) 的時(shí)間取得浪費(fèi)的空間。
4. 選最小浪費(fèi)%1000000007後回傳。
5. 該 long long 的記得 long long 。


source code

創(chuàng)作回應(yīng)

相關(guān)創(chuàng)作

更多創(chuàng)作