免费psd图片素材网站,北太平庄网站建设,seo哪家强,看电视剧的免费网站大全倍增法
倍增法#xff08;Binary Lifting#xff09;#xff0c;顾名思义#xff0c;就是利用“以翻倍的速度增长”的思想来解决问题的一类算法#xff0c;它能够使线性的处理转化为对数级的处理#xff0c;大大地优化时间复杂度。这个方法在很多算法中均有应用#xf…倍增法
倍增法Binary Lifting顾名思义就是利用“以翻倍的速度增长”的思想来解决问题的一类算法它能够使线性的处理转化为对数级的处理大大地优化时间复杂度。这个方法在很多算法中均有应用其中最常用的是 RMQ 问题和求 LCA最近公共祖先。
下面介绍如何使用倍增法在有序的序列中查找满足条件的位置。
题目描述
给定一个单调不降的序列以及 m m m个查询每个查询是一个数字 k k k查找第一个大于等于 k k k的位置。
输入格式
第一行 n n n 和 m m m
第二行 n n n 个元素的序列
第三行 m m m 个数字表示 m m m 个查询的 k k k 每个查询的 k k k确保在序列的最大值范围内。
输出格式 m m m 个数字表示第一个大于等于 k k k 的位置用空格隔开。
样例输入
10 1
1 2 3 4 6 6 6 8 9 10
6样例输出
5数据范围
20%的数据 1 ≤ n , m ≤ 1000 1\le n,m\le 1000 1≤n,m≤1000100%的数据 1 ≤ n , m ≤ 1 0 5 1\le n,m\le 10^5 1≤n,m≤105 1 ≤ 1\le 1≤所有元素 ≤ 1 0 9 \le 10^9 ≤109所有 1 ≤ k ≤ 1\le k \le 1≤k≤序列最大值
算法思想
在单调不降的序列中查找一个大于等于 k k k 的位置朴素的做法是从位置 1 1 1开始判断不满足要求则每次向右移动 1 1 1个位置重复进行直到找到满足条件的位置时间复杂度为 O ( n ) O(n) O(n)。
倍增法也从位置 1 1 1开始判断如果该位置上的数小于 k k k则将移动的距离增加 1 1 1倍然后向右移动否则如果该位置上的数大于等于 k k k则将移动的距离减半继续判断。重复进行直到不能移动为止时间复杂度为 O ( l o g n ) O(logn) O(logn)。
移动过程如下图所示 查找结束后会停留在最后一个小于 k k k的位置上。
代码实现
#include iostream
using namespace std;
const int N 5e5 10;
int a[N];
int main()
{int n, m, k;scanf(%d%d, n, m);for(int i 1; i n; i ) scanf(%d, a i);while(m --) {scanf(%d, k);//x表示位置p表示增加距离int x 0, p 1;while(p ! 0) {//x位置上的数小于k则将移动的距离增加1倍if(x p n a[x p] k) {x p;p * 2;}//x位置上的数大于等于k则将移动的距离减半else p / 2;}//x最终停留在最后一个小于k的位置上应输出x 1printf(%d , x 1); }
}
