如何做博客网站,人才市场网站源码,建站公司建的网站能改动吗,wordpress迁移后栏目打开404文章目录 二分第一类第二类 前缀和原题链接题目描述输入格式输出格式数据范围输入样例#xff1a;输出样例#xff1a; 题目分析示例代码 二分
二分法是我们在高中数学就学习过的一种思想#xff0c;他也是一种效率较高的查找算法#xff0c;在编写代码的过程中#xff0… 文章目录 二分第一类第二类 前缀和原题链接题目描述输入格式输出格式数据范围输入样例输出样例 题目分析示例代码 二分
二分法是我们在高中数学就学习过的一种思想他也是一种效率较高的查找算法在编写代码的过程中初学者很容易就会陷入死循环
二分的基本步骤如下
第一步是需要确定一个区间使得我们的目标值一定是在区间中出现的
第二步需要确定一个性质使得这个性质满足两点第一点是可以根据这个性质把这个区间分为左和右连续的两段第二点是我们最终的答案一定是二分的某一个分界点绝大多数
整数二分是很容易出现死循环的一种情况因为整数是离散的因此对应的答案在边界的情况也是两种 其实相对应的我们也可以将二分分为两大类一种是答案在左边的终点另一种是答案在右边的起点
我们来具体看一下这两种问题是如何二分的
第一类
目标值在红色区间的右端点
我们把区间进行标注如图 M是L和R的中点其实就把区间[L,R]分成[L,M-1]和[M,R]
分成两段之后我们只需要判断M的颜色(性质)如果是在红色区间就说明目标值一定在绿色区间[M,R]内否则说明目标值在红色区间[L,M-1]内
对应到代码上我们可以这样写
while (L R)
{M (L R 1) / 2;if (M 红)L M;elseR M - 1;
}这里需要注意的就是当答案在左边区间的最后一位时由于C/C会自动下取整这里算中点时就需要补上1这样就不会漏判死循环了当然这里也可以更改判断条件例如LR同样也不会出现死循环
这里有个简单的判断是否需要补上1就是看我们在判断的时候如果写的是LM加上1就可以了
第二类
目标值是绿色区间的左端点
将[L,R]分成[L,M]和[M1,R]如果M是绿色说明目标值在红色区间[L,M]否则就是在绿色区间[M1,R]
这里我们可以给出相应的代码
while (L R)
{M (L R) / 2;if (M 绿)R M;elseL M 1;
}同样的我们也是只要看判断之后的赋值语句即可当L M时则需要加上1当R M时则不需要加
前缀和
前缀和其实是一种快捷的求和的思想是用于求一个静态区间的任意位置之间的所有数的和的思想
这里我们直接结合最基础的例题来理解
原题链接
795. 前缀和
题目描述
输入一个长度为 n 的整数序列。
接下来再输入 m 个询问每个询问输入一对 l,r。
对于每个询问输出原序列中从第 l 个数到第 r 个数的和。
输入格式
第一行包含两个整数 n 和 m。
第二行包含 n 个整数表示整数数列。
接下来 m 行每行包含两个整数 l 和 r表示一个询问的区间范围。
输出格式
共 m 行每行输出一个询问的结果。
数据范围
1≤l≤r≤n, 1≤n,m≤100000, −1000≤数列中元素的值≤1000
输入样例
5 3
2 1 3 6 4
1 2
1 3
2 4 输出样例
3
6
10 题目分析
这里就是给出一个静态序列有m次询问每次给一对l和r需要分别输出从l到r的总和
如果我们暴力做的话就是每一次都需要从l加到r并且每一次循环都是O(n)的时间复杂度
一旦当询问次数较大时时间效率就会非常低
那么这时我们就会需要用到前缀和的思想他非常的基础和重要也是笔者最先开始学习的算法之一
我们把之前的那个静态序列标记为 a i a_i ai,表示第i项然后我们来构建一个新的序列 s i s_i si代表他是原序列中前i个数字的和
其中 s i a 1 a 2 ⋯ a i s_i a_1 a2 \dots a_i sia1a2⋯ai
特殊规定 s 0 0 s_0 0 s00
这样我们就可以发现一个规律 s i s i − 1 a i s_i s_{i-1} a_i sisi−1ai
我们可以根据这个公式递推出s序列中的所有数字
for(int i 1; i n; i)
{s[i] s[i-1] a[i];
}这一步骤就叫做前缀和也是我们之后求和的预处理工作
当我们想算从l到r的和时可以这样 a l a l 1 a l 2 ⋯ a r a_l a_{l1} a_{l2} \dots a_r alal1al2⋯ar a 1 a 2 ⋯ a l − 1 a l a l 1 a l 2 ⋯ a r − a 1 − a 2 − ⋯ − a l − 1 a_1 a_2 \dots a_{l-1} a_l a_{l1} a_{l2} \dots a_r - a_1 - a_2 - \dots - a_{l-1} a1a2⋯al−1alal1al2⋯ar−a1−a2−⋯−al−1 s r − s l − 1 s_r - s_{l-1} sr−sl−1
所以当我们预处理结束之后我们只需要计算两个数的差即可这样的时间复杂度就达到了O(1)是质的飞跃
对于计算区间和还有其他的方法例如树状数组和线段树这个我们以后会讲解而对于前缀和来说他的局限性就在于序列只能是静态的序列一旦其中的某个数值被修改就需要重新计算前缀和而树状数组和线段树是可以实现边查边算的
示例代码
#includeiostream
using namespace std;const int N 1e510; // 数据范围
int n,m;
long long arr[N]; // 原数组
long long pre[N]; // 前缀和数组int main()
{cin n m;for(int i1;in;i) // 数据输入{cinarr[i];pre[i] pre[i-1] arr[i]; // 前缀和初始化}while(m--){int l,r;cinlr;coutpre[r] - pre[l-1]\n;}return 0;
}
