当前位置： 移动技术网 > IT编程>开发语言>C/C++ > UOJ#52. 【UR #4】元旦激光炮(交互)

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

2018年07月30日  | 移动技术网IT编程  | 我要评论

遗爱记 蓝白色,创意设计大赛,你的名字资源

题意

给出三个已经排好序的数组$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;
}

 

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网