用C++倍增的方法完成:一个含有n项的单调不减的数列a,给定一个数m,在数列a中找到最大的小于m的数,输出这个数,如果找不到则输出-1。
时间: 2024-05-10 19:21:28 浏览: 8
```
#include <stdio.h>
#define MAXN 100000
int n, m, a[MAXN + 5], f[MAXN + 5][20];
void init() {
for (int i = 1; i <= n; i++) f[i][0] = a[i];
for (int j = 1; (1 << j) <= n; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
f[i][j] = f[i][j - 1] > f[i + (1 << (j - 1))][j - 1] ? f[i][j - 1] : f[i + (1 << (j - 1))][j - 1];
}
int query(int l, int r) {
int k = 0;
while ((1 << (k + 1)) <= r - l + 1) k++;
return f[l][k] < m ? f[l][k] : -1;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
init();
int ans = -1;
for (int i = n; i >= 1; i--) {
if (a[i] < m) {
ans = query(1, i);
break;
}
}
printf("%d\n", ans);
return 0;
}
```