时间上的优化,可以从O(BlogB)优化到O(B)
查看原帖
时间上的优化,可以从O(BlogB)优化到O(B)
185167
Guxue楼主2021/6/7 08:09

几个题解的写法好像都是枚举mid然后再枚举l、r跑(l、r指最小和最大的满意度),但事实上会发现对于递增的l,r同样是递增的。所以我们只需要从1开始枚举l,再从1开始枚举r,如果成功匹配了就l++,r不用重置,这样的复杂度为O(2*B),应该是要更优的

2021/6/7 08:09
加载中...