排序题的自适应交互库最快能做到什么复杂度?
  • 板块学术版
  • 楼主WYXkkZzz Zzz
  • 当前回复16
  • 已保存回复16
  • 发布时间2024/10/17 16:41
  • 上次更新2024/10/17 19:20:05
查看原帖
排序题的自适应交互库最快能做到什么复杂度?
130151
WYXkkZzz Zzz楼主2024/10/17 16:41

标题的意思是,你需要实现下面这题的自适应交互库:

交互题。有一堆未知数 a1a_1ana_n 互不相同,你需要给出它们的排序。你获取信息的方式只有调用 compare(i,j) 来得到 aia_iaja_j 的大小关系。

此处假设对于未被此前的询问确定的大小关系一律随机返回一个值。

实际上等价于下面的表述:

维护一个 nn 个点的有向图,初始为空。支持增加一条边,或者查询两个点之间是否有一条单向路及其方向。保证图永远无环。

2024/10/17 16:41
加载中...