File tree Expand file tree Collapse file tree 1 file changed +2
-2
lines changed Expand file tree Collapse file tree 1 file changed +2
-2
lines changed Original file line number Diff line number Diff line change @@ -31,8 +31,8 @@ public:
31
31
};
32
32
```
33
33
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]] ` 的商品,这是一种贪心,然后他能覆盖的货物的所有空间可以用前缀和优化。
35
35
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要大 ,届时肯定会产生更多浪费。
37
37
38
38
也可以使用双指针来做这部分快速查找满足条件的下标。
You can’t perform that action at this time.
0 commit comments