UOJ#52. 【UR #4】元旦激光炮(交互)
2018-08-02 05:43:54来源:博客园 阅读 ()
题意
给出三个已经排好序的数组$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; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- P2280 [HNOI2003]激光炸弹 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash