Skip to content

Commit eee4ce8

Browse files
committed
排序+前缀和+二分/双指针+贪心
1 parent 3ba32cf commit eee4ce8

File tree

1 file changed

+2
-2
lines changed

1 file changed

+2
-2
lines changed

leetcode/2100-2200/1889..md

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -31,8 +31,8 @@ public:
3131
};
3232
```
3333

34-
注意数据量,由于$sum(boxes[i]) ≤ 1e5$,所以,可以先排序,再枚举每一组$boxes$中每个盒子能承载的货物,只需要去枚举$boxes[i][j]$在商品中距离$boxes[i][j - 1]$的最小距离即可,因为$boxes[i][j - 1]$处理掉了比它小的所有商品,因此只需要考虑$(boxes[i][j - 1], boxes[i][j]]$的商品,这是一种贪心,然后他能覆盖的货物的所有空间可以用前缀和优化。
34+
注意数据量,由于`sum(boxes[i]) ≤ 1e5`,所以,可以先排序,再枚举每一组`boxes`中每个盒子能承载的货物,只需要去枚举`boxes[i][j]`在商品中距离`boxes[i][j - 1]`的最小距离即可,因为`boxes[i][j - 1]`处理掉了比它小的所有商品,因此只需要考虑`(boxes[i][j - 1], boxes[i][j]]`的商品,这是一种贪心,然后他能覆盖的货物的所有空间可以用前缀和优化。
3535

36-
可以很容易发现,对于每个$boxes[i]$应用这样的策略,一定是最优的,假如说不是$boxes[i][j]$的盒子来装填$(boxes[i][j - 1], boxes[i][j]]$的空间,那么能满足条件的盒子,一定比$boxes[i][j]$要大,届时肯定会产生更多浪费。
36+
可以很容易发现,对于每个`boxes[i]`应用这样的策略,一定是最优的,假如说不是`boxes[i][j]`的盒子来装填`(boxes[i][j - 1], boxes[i][j]]`的空间,那么能满足条件的盒子,一定比`boxes[i][j]`p要大,届时肯定会产生更多浪费。
3737

3838
也可以使用双指针来做这部分快速查找满足条件的下标。

0 commit comments

Comments
 (0)