LeetCode 1889. 装包裹的最小浪费空间
原题链接
困难
作者:
ITNXD
,
2021-06-08 13:51:41
,
所有人可见
,
阅读 332
详细请查看注释内容
参考代码:
typedef long long LL;
const LL mod = 1e9 + 7, INF = 1e18;
/*
不能二分每个包裹放到哪个箱子,数量级太高!
反过来可以这样:
二分每个箱子在包裹序列的位置(小于等于该箱子的最后一个包裹位置)
二分出来的每个箱子位置,可以将该包裹序列分为若干段,每一段都应该放入其之后的最近的箱子内!
总浪费空间:要减去所有包裹的总尺寸sum,再加上每种箱子的尺寸乘以其使用的数量!
时间复杂度:由于箱子总数量为1e5,因此最对会进行1e5log1e5次运算!
注意:防止爆int,使用LL
*/
class Solution {
public:
int minWastedSpace(vector<int>& a, vector<vector<int>>& bs) {
sort(a.begin(), a.end());
// 包裹尺寸总和
LL sum = 0;
for(int i = 0; i < a.size(); i ++) sum += a[i];
int n = a.size();
LL res = INF;
for(auto &b : bs){
sort(b.begin(), b.end());
// 若最大箱子尺寸都小于包裹尺寸,则直接跳过
if(b.back() < a.back()) continue;
// t初值先将所有包裹尺寸减去
LL last = -1, t = -sum;
// 二分每个箱子在包裹序列的位置(小于等于该箱子的最后一个包裹位置)
for(auto x : b){
int l = last, r = n - 1;
while(l < r){
int mid = l + r + 1 >> 1;
if(a[mid] <= x) l = mid;
else r = mid - 1;
}
// 该箱子无处可放,直接跳过
if(r == last) continue;
// 累加区间[last + 1, r]使用的x类型尺寸的箱子的总空间
t += (r - last) * x;
// 更新区间左端点
last = r;
}
// 更新答案
res = min(res, t);
}
if(res == INF) return -1;
return res % mod;
}
};