比较巧妙的一道交互题.
裸做的话询问次数是 $O( 3log^2 n)$,即先二分答案,然后在 3 个序列中验证.
正解的话考虑先询问 3 个序列中第 $frac{k}{3}$ 小的数.
令 3 个序列中最小的数为 $x$,则我们在 3 个序列中取出的这 $k$ 个数一定有小于等于 $k$ 个数小于等于 $x$.
而对于 $ans$ 的要求是要有 $k$ 个数小于等于 $ans$,故 $ans$ 一定大于等于这个最小值.
故贡献这个最小值所在的序列的前 $frac{k}{3}$ 个数一定都小于等于 $ans$,所以我们就将 $k$ 的规模乘了 $frac{2}{3}$.
总询问次数小于等于 $99$.
#include<iostream> int minn(int x,int y){return x<y?x:y;}; int query_kth(int n_a, int n_b, int n_c, int k) { int pa=0,pb=0,pc=0,tmin; while(k) { int l=(k-2)/3; int t1=get_a(pa+l); int t2=get_b(pb+l); int t3=get_c(pc+l); tmin=minn(minn(t1,t2),t3); l++; if(tmin==t1) pa+=l; else if(tmin==t2) pb+=l; else if(tmin==t3) pc+=l; k-=l; } return tmin; }