2.求解查找最后一个小于等于指定数的元素问题 给定一个长度为n的单调递增的正整数序列,即序列中的每一个数都比前一个数大,有m个询问,每次询问一个x,问序列中最后一个小于等于x的数是什么? 输入描述:给定一个长度为n的单调递增的正整数序列, 即序列中的每一个数都比前一个数大,有m个询问,每次询问一个x。 输出描述:输出共m行,表示序列中最后一个小于等于x的数是多少。如果没有,输出-1。 样例输入: 5 3 1 2 3 4 6 5 1 3 样例输出: 4 1 3使用c++写出完整代码,要求使用动态规划或者贪心算法、回溯算法、分支限界算法的一种
时间: 2024-03-25 20:37:46 浏览: 95
实验4-求解元素查找的问题-分治法.doc
以下是使用二分查找的代码实现:
```c++
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
while (m--) {
int x;
cin >> x;
int left = 0, right = n - 1, res = -1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] <= x) {
res = nums[mid];
left = mid + 1;
} else {
right = mid - 1;
}
}
cout << res << endl;
}
return 0;
}
```
其中,我们使用二分查找在单调递增的正整数序列中查找最后一个小于等于x的数。具体实现如下:
首先初始化左右指针left和right,分别指向序列的开头和结尾。然后在循环中,每次计算中间位置mid,如果中间位置的值小于等于x,那么说明最后一个小于等于x的数在mid的右边,因此记录下mid位置的值,并将左指针left移到mid+1位置继续查找;否则最后一个小于等于x的数在mid的左边,将右指针right移到mid-1位置继续查找。
最终,如果找到了最后一个小于等于x的数,那么输出该数;否则输出-1。
阅读全文