请教这道题二分答案的复杂度
  • 板块P2440 木材加工
  • 楼主GaIaxy
  • 当前回复10
  • 已保存回复10
  • 发布时间2023/11/8 14:40
  • 上次更新2023/11/8 17:23:12
查看原帖
请教这道题二分答案的复杂度
1060148
GaIaxy楼主2023/11/8 14:40

二分的复杂度是O(log(L)),但是不是基于check函数是O(1)的前提?本题check函数的复杂度要遍历所有的树是O(n),有点不太懂这里的复杂度是O(nlog(L))吗,为什么没有TLE

while(l < r){
  mid = (l + r + 1) / 2;
  if(check(mid)) l = mid;
  else r = mid - 1;
}
2023/11/8 14:40
加载中...