二分练习题3 查找小于x的最大元素 题解
2024-09-01 08:45:32
题目描述
现在告诉你一个长度为 \(n\) 的有序数组 \(a_1, a_2, ..., a_n\) ,以及 \(q\) 次询问,每次询问会给你一个数 \(x\) ,对于每次询问,你需要输出数组 \(a\) 中小于 \(x\) 的最大元素。
输入格式
输入的第一行包含一个整数 \(n(1 \le n \le 100000)\) ,用于表示数组中元素的个数。
输入的第二行包含 \(n\) 个整数,两两之间有一个空格,用于表示数组中的元素 \(a_1, a_2, ..., a_n(1 \le a_i \le 10^9,并且 a_1 \le a_2 \le ... \le a_n)\) 。
输入的第三行包含一个整数 \(q(1 \le q \le 100000)\) ,用于表示询问的次数。
接下来 \(q\) 行,每行包含一个整数 \(x(1 \le x \le 10^9)\) ,表示要询问的数。
输出格式
对于每一次询问的 \(x\) ,如果数组 \(a\) 中存在小于 \(x\) 的元素,则输出数组 \(a\) 中满足小于 \(x\) 条件的所有元素中最大的元素;否则输出“-1” 。每个输出结果占单独的一行。
样例输入
5
3 5 7 9 11
3
2
9
15
样例输出
-1
7
11
题目分析
本题涉及算法:二分。
本题思路和上一题——《查找大于等于x的最小元素》——类似。
我们同样还是在初始时开一个 \(L = 1\) ,开一个 \(R = n\) (分别表示左右边界),开一个 \(res = -1\) (用于记录小于 \(x\) 的最大的数的坐标)。
满足循环条件 \(L \le R\) 时使 \(mid = (L+R)/2\) ,并判断:
- 如果 \(a[mid] \lt x\) (满足条件),则更新 \(res\) 为 \(mid\) ,同时 \(L = mid + 1\) ;
- 否则(不满足条件,即 \(a[mid] \ge x\) ),\(R = mid - 1\)
实现代码如下:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n, a[maxn], q, x;
// solve函数用于返回大于等于x的最小元素
int solve(int x) {
int L = 1, R = n, res = -1;
while (L <= R) {
int mid = (L + R) / 2;
if (a[mid] < x) {
res = mid;
L = mid + 1;
}
else R = mid - 1;
}
if (res == -1) return -1; // 如果循环结束res==-1,说明没有找到答案
return a[res]; // 因为res存的是最优解的坐标,所以返回a[res]
}
int main() {
cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
cin >> q;
while (q --) {
cin >> x;
cout << solve(x) << endl;
}
return 0;
}
最新文章
- android dialog
- 将不确定变成确定~Uri文本文件不用浏览器自动打开,而是下载到本地
- (转)PHP常用函数
- 前端js的书写规范和高效维护的方案_自我总结使用的方案
- 图片无法显示,载入制定url失败
- i18next-页面层语言国际化js框架介绍
- 关于全局变量和函数,在其他类中调用问题,extern关键字
- HDU 4116 Fruit Ninja
- JavaScript跨域深入研究与解决办法(转)
- 如何让msvsmon.exe 以服务方式运行
- poj2155一个二维树状数组
- [SDOI2017]数字表格
- javascript入门篇(三)
- jeffy-vim-v3.1.tar.gz
- 软件工程个人项目作业 Individual Project
- 如何把jar包发布到maven私服
- Python之路----内置函数补充与匿名函数
- 转 Fiddler导出jmeter脚本
- python---基础知识回顾(六)网络编程
- Carrer Day有感
热门文章
- 7.4 元组tuple类型内置方法
- java秒杀系列(2)- 页面静态化技术
- Sqlserver 存储过程中使用事务
- 帝国CMS(EmpireCMS) v7.5 后台XSS漏洞分析
- Android Studio和 adb 的一些常用技巧
- HackerRank - maximum-gcd-and-sum
- ABP虚拟文件系统(VirtualFileSystem)实例------定制菜单栏显示用户姓名
- WPF 浏览PDF 文件
- Storm 系列(八)—— Storm 集成 HDFS 和 HBase
- 体验SpringCloud Gateway