UOJ#52. 【UR #4】元旦激光炮(交互)
2024-08-27 03:26:37
题意
给出三个已经排好序的数组$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 = , nowb = , nowc = , mi;
while(k) {
int cur = (k - ) / ;
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;
}
最新文章
- 前端MVC学习总结(一)——MVC概要与angular概要、模板与数据绑定
- C#RSA算法实现+如何将公钥为XML格式转为PEM格式,给object-C使用
- Delphi数组
- IOS跳转设置页面及其他各种跳转页面设置
- JavaScript正则验证邮箱
- Struts2技术内幕----深入解析Struts2架构与设计(一)
- poj2840
- 使用vs code实现git同步
- 完美实现身份证校验 js正则
- jsp连接书库DatabaseUtil类
- TCP TIME WAIT
- silverlight用Encoding.UTF8读取shape文件的中文属性值 出现乱码
- 树莓派3b安装Apache2+PHP+MySQL+phpyadmin
- Python的itertools模块
- 如何搭建http服务仓库
- geo-经纬度计算
- 019-centos的yum用法
- git server side hook 试用
- java接口定义和作用
- django操作多数据库
热门文章
- Spark基本原理
- p1694猴子 并查集
- SDUT OJ 1221 亲和数 (找出某个数n所有的因子数,只需要暴力:2->;sqrt(n) 即可 )
- nodejs api 中文文档
- MYSQL进阶学习笔记九:MySQL事务的应用!(视频序号:进阶_21-22)
- nginx网站日志配置
- I.MX6 新版u-boot分析
- [Selenium] Selenium find Element Examples
- [JSOI 2007] 字符加密
- 任务47:Identity MVC:ReturnUrl实现