[交互题] UOJ52. [UR #4] 元旦激光炮

每次得到每个序列的第 \(\lfloor \frac{k}{3} \rfloor\) 小的数,则 \(3\) 个数中最小的数的排名一定小于 \(k\)

直接扔掉它及其前面的,继续这一过程。 这样是每次减少 \(\frac{1}{3}\) ,是 \(\log_{2/3} n\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include "kth.h"
#include<bits/stdc++.h>
using namespace std;
int query_kth(int na,int nb,int nc,int K){
int La=0,Lb=0,Lc=0,va,vb,vc;
while(K>2){
va=get_a(La+K/3-1); vb=get_b(Lb+K/3-1); vc=get_c(Lc+K/3-1);
if(va<=vb&&va<=vc) La+=K/3;
else if(vb<=va&&vb<=vc) Lb+=K/3;
else if(vc<=va&&vc<=vb) Lc+=K/3;
K-=K/3;
}
static int q[10];
for(int i=La;i<=La+2;i++) q[++q[0]]=get_a(i);
for(int i=Lb;i<=Lb+2;i++) q[++q[0]]=get_b(i);
for(int i=Lc;i<=Lc+2;i++) q[++q[0]]=get_c(i);
sort(q+1,q+1+q[0]); return q[K];
}