给定一定长度为 n 的单调递增的正整数序列,即序列中的每一个数都比前一个大,有 m 个询问,每次询问一个 x,问序列中最后一个小于等于 x 的数是什么? n<=100000给定一个长度为 n 的单调递增的正整数序列,即序列中的每一个数都比前一个数大,有 m 个询问, 每次询问一个 x。输出共 m 行,表示序列中最后一个小于等于 x 的数都是多少。如果没有输出 - 1。用C语言编程
时间: 2024-01-22 07:19:18 浏览: 101
动态规划问题-最长单调递增子序列问题
以下是 C 语言的代码实现:
```c
#include <stdio.h>
int main() {
int n, m, i, j, x, ans;
int a[100000];
scanf("%d%d", &n, &m);
for (i = 0; i < n; ++i) {
scanf("%d", &a[i]);
}
for (j = 0; j < m; ++j) {
scanf("%d", &x);
ans = -1;
for (i = 0; i < n; ++i) {
if (a[i] > x) {
break;
}
ans = a[i];
}
printf("%d\n", ans);
}
return 0;
}
```
代码思路如下:
首先输入序列长度 n 和询问次数 m,以及整数序列 a。
之后,对于每次询问,输入一个整数 x,并将答案初始化为 -1。
接着,从前往后遍历整个序列 a,如果当前元素比 x 大,则退出循环;否则,将答案更新为当前元素值。
最后,输出答案即可。
需要注意的是,如果循环结束后答案仍然是 -1,说明整个序列中没有小于等于 x 的数,需要输出 -1。
阅读全文