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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏用户2442861的专栏

awk工作常用技巧

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/d...

10220
来自专栏kevin-blog

acm C语言求两个数最大值

68910
来自专栏小樱的经验随笔

洛谷P1313 计算系数【快速幂+dp】

P1313 计算系数 题目描述 给定一个多项式(by+ax)^k,请求出多项式展开后x^n*y^m 项的系数。 输入输出格式 输入格式: 输入文件名为facto...

22850
来自专栏机器学习算法与Python学习

Numpy

Numpy Numpy是Python中用于科学计算的核心库。它提供了高性能的多维数组对象,以及相关工具。(本文文末的原文链接为numpy的官方文档) NumPy...

35470
来自专栏mathor

LeetCode342. 4的幂

 这是上一道题2的幂的进阶,首先我们看和2的幂有什么不同。2的幂有1,2,4,8......,而4的幂有1,4,16,64,也就是说少了2,8,32......

9820
来自专栏数据结构与算法

1265. [NOIP2012] 同余方程

1265. [NOIP2012] 同余方程 ★☆   输入文件:mod.in   输出文件:mod.out 简单对比 时间限制:1 s   内存限制:128 M...

34760
来自专栏西枫里博客

单数据和批量数据的删除操作

通常对某条数据的删除和某一批数据的删除分别采用两个成员方法。这样太累赘了一些,为了使用批量删除的成员方法,就需要构造单数据的结构。这里以ID为数组作为例子

10030
来自专栏云霄雨霁

字符串查找----查找算法的选择

31100
来自专栏Hongten

一个demo告诉你优化算法的强大

11320
来自专栏C/C++基础

迷宫问题(maze problem)——深度优先(DFS)与广度优先搜索(BFS)求解

给定一个迷宫,指明起点和终点,找出从起点出发到终点的有效可行路径,就是迷宫问题(maze problem)。

2.2K20

扫码关注云+社区

领取腾讯云代金券