给定一个长度为n的单调递增的正整数序列,即序列中的每一个数都比前一个数大,有m个询问,每次询问一个x,问序列中最后一个小于等于x的数是什么?声称代码
时间: 2024-02-20 16:02:21 浏览: 147
好的,以下是 C++ 代码实现:
```cpp
#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;
int ans = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= x) {
ans = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
if (ans != -1) {
cout << nums[ans] << endl;
} else {
cout << "No answer" << endl;
}
}
return 0;
}
```
思路是二分查找,每次判断中间位置的数是否小于等于 x,如果是,则更新答案,并在右半部分查找;否则,在左半部分查找。最终得到的答案就是最后一个小于等于 x 的数。
阅读全文