UOJ#52. 【UR #4】元旦激光炮(交互)

題意

給出三個已經排好序的數組$a, b, c$

在$100$次詢問內找出第$k$小的元素

Sol

一種很顯然的$log^2n$的做法：首先在$a$中二分，然後再$b,c$中二分。這樣可以得到$60$分的好成績。

然而這演算法就沒什麼優化的空間了。。。

考慮另一種做法。

我們每次對三個數組詢問第$\frac{3}{k}$個數。

然後我們可以直接把最小對應的那一段拋棄。正確性顯然吧。或者你可以考慮一下最壞情況

那麼$k$就縮小了$\frac{1}{3}$

算一下，查詢次數不會超過$99$。

具體可以這麼算

邊界好難調啊，還是Orz std吧

#include "kth.h"
#include <stdio.h>
#include <assert.h>
#include<algorithm>
using namespace std;
int query_kth(int n_a, int n_b, int n_c, int k) {
    int nowa = 0, nowb = 0, nowc = 0, mi;
    while(k) {
        int cur = (k - 2) / 3;
        int vala = get_a(nowa + cur),
            valb = get_b(nowb + cur), 
            valc = get_c(nowc + cur);
        mi = min(vala, min(valb, valc));
        cur++;
        if(mi == vala) nowa += cur;
        else if(mi == valb) nowb += cur;
        else nowc += cur;
        k -= cur;
    }
    return mi;
}