AC. 梦想

frank_c1

[UOJ 52] 元旦激光炮

发布于2017年04月14日 | 暂无评论 | 177阅读 | 倍增

题意简述

交互题。

交互库有三个数组a,b,c,长度为n_a, n_b, n_c。数组元素均是单调不降的。

你可以指定一个下标p,询问a_pb_pc_p。如果不存在返回2 ^ {31} - 1

求在100次询问内确定三个数组合并后第k小的元素。

0 \le n_a, n_b, n_c \le 10 ^ 5, 1 \le k \le n_a + n_b + n_c, 1 \le a_i, b_i, c_i \le 10 ^ 9

算法讨论

很长一段时间都只会两个\log的暴力。

直到我看到了标算神做法。确实没有想到。

考虑迭代减少k的规模。设当前k = k_0,我们取p = \lfloor \frac{k} {3} \rfloor,查询a'_{p}, b'_{p}, c'_{p}。取h = \min(a'_{p}, b'_{p}, c'_{p})

那么由于3 p \le kh必定不超过答案,也就是说h对应数组的前p项可以舍弃了,而k也因此缩小到了原来的\frac{2} {3}。直到k迭代到小于3时我们开始暴力查询。可以证明这样的复杂度是O(\log_{\frac{3} {2}} {k})的,就可以愉快地通过啦。