難度: Hard
目前下列解法的時間複雜度: O( |包裹|*lg(|包裹|) + |所有箱子|*lg(max(|所有箱子|,|包裹|)) )
題目說明
給定一堆包裹及一堆箱子供應商。每個包裹有一個大小;每個箱子有一個容量。
選擇一個箱子供應商(供應多種箱子,每種箱子無限供應),每個包裹使用一個箱子裝箱,用此供應商的箱子裝完所有包裹,計算最少空間浪費(=箱子容量-包裹大小)總和。
問所有箱子供應商中,可以達成的最小浪費為何。若沒有任何一個箱子供應商可以提供夠大的箱子裝下最大的包裹,則回傳 -1 。
解法: just do it
1. 把包裹排序,並建立包裹 prefix sum 。
2. 分別對每個箱子供應商的箱子排序
3. 從小箱子到大箱子,每個箱子花 O(lg(|包裹|) 的時間取得浪費的空間。
4. 選最小浪費%1000000007後回傳。
5. 該 long long 的記得 long long 。
source code