一个人做网站好做吗,如何优化关键词搜索,网站栏目词,网站开发合同 doc目录前言一、二分算法1.1 二分查找1.1.1 牛可乐和魔法封印1.1.2 A - B 数对1.1.3 烦恼的高考志愿结语#x1f3ac; 云泽Q#xff1a;个人主页#x1f525; 专栏传送入口: 《C语言》《数据结构》《C》《Linux》《蓝桥杯系列》⛺️遇见安然遇见你#xff0c;不负代码不负卿~ …目录前言一、二分算法1.1 二分查找1.1.1 牛可乐和魔法封印1.1.2 A - B 数对1.1.3 烦恼的高考志愿结语 云泽Q个人主页 专栏传送入口: 《C语言》《数据结构》《C》《Linux》《蓝桥杯系列》⛺️遇见安然遇见你不负代码不负卿~前言大家好啊我是云泽Q欢迎阅读我的文章一名热爱计算机技术的在校大学生喜欢在课余时间做一些计算机技术的总结性文章希望我的文章能为你解答困惑~一、二分算法二分算法是我觉得在基础算法篇章中最难的算法二分算法的原理以及模板其实是很简单的主要的难点在于问题中的各种各样的细节问题。因此大多数情况下只是背会二分模板并不能解决题目还要去处理各种乱七八糟的边界问题1.1 二分查找在排序数组中查找元素的第一个和最后一个位置算法原理当我们的解具有二段性时就可以使用二分算法找出答案根据待查找区间的中点位置分析答案会出现在哪一侧接下来舍弃一半的待查找区间转而在有答案的区间内继续使用二分算法查找结果模板二分的模板在网上至少能搜出来三个以上。但是我们仅需掌握一个并且一直使用下去即可为了防止溢出求中点时可以下面的方式mid l (r - l) / 2;时间复杂度每次二分都会去掉一半的查找区域因此时间复杂度为logN模板记忆方式不用死记硬背算法原理搞清楚之后在分析题目的时候自然而然就知道要怎么写二分的代码仅需记住一点if/else 中出现 -1 的时候求 mid 就 1 就够了二分问题解决流程先画图分析确定使用左端点模板还是右端点模板还是二者配合一起使用二分出结果之后不要忘记判断结果是否存在二分问题众多一定要分析全面STL中的二分查找algorithmlower_bound在 [first, last) 区间内返回第一个大于等于 target 的元素的迭代器若所有元素都小于 target返回 last。时间复杂度OlogNupper_bound在 [first, last) 区间内返回第一个大于 target 的元素的迭代器若所有元素都小于等于 target返回 last。时间复杂度OlogN二者均采用二分实现。但是STL中的二分查找只能适用于“在有序的数组中查找”如果是二分答案就不能使用因此还是需要记忆二分模板解法一二分查找模板classSolution{public:vectorintsearchRange(vectorintnums,inttarget){intnnums.size();//若整个数组没有数后面会发生越界访问if(n0)return{-1,-1};//初始化intleft0,rightn-1;//起始位置while(leftright){intmid(leftright)/2;if(nums[mid]target)rightmid;elseleftmid1;}//left 或 right所指的位置就有可能是最终结果if(nums[left]!target)return{-1,-1};intretleftleft;//终止位置left0,rightn-1;while(leftright){intmid(leftright1)/2;if(nums[mid]target)leftmid;elserightmid-1;}//若有起始位置一定有终止位置return{retleft,right};}};解法二STL中的二分查找classSolution{public:vectorintsearchRange(vectorintnums,inttarget){//找到第一个 target 的迭代器autoleftlower_bound(nums.begin(),nums.end(),target);//迭代器越界或指向的元素不是targetif(leftnums.end()||(*left)!target)return{-1,-1};//找到第一个 target 的迭代器autorightupper_bound(nums.begin(),nums.end(),target);return{//转化为下标(int)(left-nums.begin()),(int)(right-nums.begin()-1)};}};一、解题思路结合两个函数的特性可直接推导目标位置起始位置lower_bound 返回的迭代器若该迭代器指向的元素等于 target则为起始位置否则说明数组中无 target直接返回 [-1, -1]。结束位置upper_bound 返回的迭代器减 1即为最后一个等于 target 的元素位置前提是起始位置有效。二、代码详细解析起始位置查找left_it lower_bound(nums.begin(), nums.end(), target)在整个数组中二分查找第一个 target 的元素。判空逻辑如果 left_it 等于 nums.end()所有元素都小于 target或*left_it ! target找到的是大于 target 的元素直接返回 [-1, -1]。结束位置查找right_it upper_bound(nums.begin(), nums.end(), target)找到第一个 target 的元素。结束位置下标 right_it - nums.begin() - 1因为 right_it 是第一个大于 target 的位置前一个就是最后一个等于 target 的位置。迭代器转下标通过 迭代器 - 容器.begin() 得到元素的下标强制转换为 int 以匹配返回值类型。1.1.1 牛可乐和魔法封印牛可乐和魔法封印没啥好说的直接分析上模板#includeiostreamusingnamespacestd;constintN1e510;inta[N];intn;intbinary_search(intx,inty){//初始化intleft1,rightn;// 大于等于 x 的最小元素while(leftright){intmid(leftright)/2;if(a[mid]x)rightmid;elseleftmid1;}if(a[left]x)return0;inttmpleft;//小于等于 y 的最大元素left1,rightn;while(leftright){intmid(leftright1)/2;if(a[mid]y)leftmid;elserightmid-1;}if(a[left]y)return0;returnleft-tmp1;}intmain(){cinn;for(inti1;in;i)cina[i];intq;cinq;while(q--){intx,y;cinxy;coutbinary_search(x,y)endl;}return0;}补充两点一if(a[left] x) return 0;与if(a[left] y) return 0;的作用1. if(a[left] x) return 0;执行时机第一个二分循环找≥x 的最小元素结束后。二分循环的特性循环条件是left right退出时left right此时left是我们 “认为” 的「≥x 的最小位置」。判断的意义如果此时a[left] x说明整个数组的所有元素都小于 x比如数组是[1,2,3,4,5]x6不存在≥x 的元素自然也不存在 “≥x 且≤y” 的元素因此直接返回 0。反例验证结合题目示例 1若输入查询x6, y10数组是[1,2,3,4,5]第一个二分结束后left5a[5]5 6触发该判断返回 0正确因为没有元素≥6。2. if(a[left] y) return 0;执行时机第二个二分循环找≤y 的最大元素结束后。二分循环的特性循环条件是left right退出时left right此时left是我们 “认为” 的「≤y 的最大位置」。判断的意义如果此时a[left] y说明整个数组的所有元素都大于 y比如数组是[1,2,3,4,5]y0不存在≤y 的元素因此直接返回 0。反例验证结合题目示例 1若输入查询x0, y0数组是[1,2,3,4,5]第二个二分结束后left1a[1]1 0触发该判断返回 0正确因为没有元素≤0。如果去掉这两行会出现逻辑错误比如数组[1,2,3,4,5]查询x6, y10第一个二分后tmp5a[5]5 6第二个二分后left5a[5]5 ≤10计算left - tmp 1 5-511但实际结果应该是 0明显错误。这两行判断正是为了堵住这类 “二分找到的位置不满足条件” 的漏洞确保只有当「存在≥x 的元素」且「存在≤y 的元素」时才会计算最终的个数。二日常开发中32 位 int取值范围在 109量级约 ±21 亿1.1.2 A - B 数对A - B 数对数据范围ai是0到230加加减减有可能超过int的范围所以可以用long long由于顺序不影响最终结果所以可以先把整个数组排序。由A-BC得BA-C由于C是已知的数我们可以从前往后枚举所有的A然后去前面找有多少个符合要求的B正好可以用二分快速查找出区间的长度。【STL的使用】lower_bound传入要查询区间的左右迭代器注意是左闭右开的区间如果是数组就是左右指针以及要查询的值k然后返回该数组中≥k的第一个位置upper_bound传入要查询区间的左右迭代器注意是左闭右开的区间如果是数组就是左右指针以及要查询的值k然后返回该数组中k的第一个位置要点补充sort(first, last)会对[first, last)区间内的元素排序包含 first 指向的元素不包含 last 指向的元素。sort(a 1, a 1 n) → 排序范围是 [a1, a1n)对应数组元素 a[1], a[2], …, a[n]正好是输入的 n 个元素。i 从 2 开始的核心原因i1 时没有可匹配的 B 元素无法形成数对遍历无意义。避免一次无效循环让代码更高效STL二分算法解法#includeiostream#includealgorithmusingnamespacestd;constintN2e510;typedeflonglongLL;intn;LL a[N];LL c;intmain(){cinnc;for(inti1;in;i)cina[i];sort(a1,a1n);LL ret0;for(inti2;in;i){LL ba[i]-c;retupper_bound(a1,ai,b)-lower_bound(a1,ai,b);}coutretendl;return0;}二分模板解法不建议#includeiostream#includealgorithmusingnamespacestd;constintN2e510;typedeflonglongLL;intn;LL a[N];LL c;intmain(){cinnc;for(inti1;in;i)cina[i];sort(a1,a1n);LL ret0;for(inti2;in;i){LL ba[i]-c;// 1. 找第一个 ≥ b 的位置左端点模板区间 [1, i-1]LL left1,righti-1;// 改用LL避免mid溢出while(leftright){LL mid(leftright)/2;if(a[mid]b){rightmid;}else{leftmid1;}}LL first_geleft;// 第一个≥b的位置// 2. 找最后一个 ≤ b 的位置右端点模板区间 [1, i-1]left1,righti-1;while(leftright){LL mid(leftright1)/2;// 右端点模板必须1if(a[mid]b){leftmid;}else{rightmid-1;}}LL last_leleft;// 最后一个≤b的位置// 3. 严谨的匹配判断区间有效 第一个≥b的元素就是bLL cnt0;if(first_gelast_lea[first_ge]b){cntlast_le-first_ge1;}retcnt;}coutretendl;return0;}说一下最后的if判断作用一、前置前提两个二分的核心结果在这段代码执行前我们通过两个模板得到了两个关键位置first_ge数组 a[1~i-1] 中第一个 ≥ b 的元素下标左端点模板结果。last_le数组 a[1~i-1] 中最后一个 ≤ b 的元素下标右端点模板结果。因为数组是升序排序的如果存在等于 b 的元素这些元素必然是一个连续的区间且这个区间的左边界就是 first_ge右边界就是 last_le。二、代码逐部分拆解1. 初始化计数LL cnt 0;先默认当前 a[i] 作为 A 时没有找到符合条件的 B计数为 0避免后续无匹配时出现垃圾值。2. 核心条件if (first_ge last_le a[first_ge] b)这是双重校验缺一不可目的是排除所有 “假匹配” 情况只保留真正存在 b 的场景。3. 计数逻辑cnt last_le - first_ge 1;当双重校验通过后说明 a[first_ge ~ last_le] 这个连续区间内的所有元素都等于 b因为数组升序且左边界≥b、右边界≤b。公式意义连续区间的元素个数 右边界 - 左边界 1比如下标 1 到 2是 2 个元素2-112。示例样例中 i3b1first_ge1last_le2则 2-112正好是 2 个 1统计正确。4. 累加计数ret cnt;将当前 a[i] 作为 A 时找到的有效 B 的个数累加到最终结果中。1.1.3 烦恼的高考志愿烦恼的高考志愿【解法】先把学校的录取分数「排序」然后针对每一个学生的成绩在「录取分数」中二分出≥b的「第一个」位置pos那么差值最小的结果要么在pos位置要么在pos一1位置。取 abs(a[pos]一b)与abs(a[pos一1]一b)两者的「最小值」即可。细节问题如果所有元素都大于b的时候pos一1会在0下标的位置有可能结果出错如果所有元素都小于b的时候pos会在n的位置此时结果倒不会出错但是我们要想到这个细节问题这道题不出错不代表下一道题不出错。加上两个左右护法结果就不会出错了。#includeiostream#includealgorithmusingnamespacestd;typedeflonglongLL;constintN1e510;intn,m;LL a[N];intfind(LL x){intleft1,rightm;while(leftright){intmid(leftright)/2;if(a[mid]x)rightmid;elseleftmid1;}returnleft;}intmain(){cinmn;for(inti1;im;i)cina[i];sort(a1,a1m);// 加上左右护法a[0]-1e710;LL ret0;for(inti1;in;i){LL b;cinb;intposfind(b);retmin(abs(a[pos]-b),abs(a[pos-1]-b));}coutretendl;return0;}代码中数据类型用long long的原因题目中明确给出了数据范围学生数 n 和学校数 m 最大可达 105学校分数线 ai​ 和学生估分 bj​ 最大可达 106这意味着单个学生的 “不满意度”即分数线与估分的绝对差最大可达 106所有学生的不满意度之和最大可达 105×1061011而在 C 中int 类型通常是 32 位其最大值约为 2.1×109远小于 1011。如果用 int 存储总和 ret必然会发生整数溢出导致结果错误。因此必须使用 64 位的 long long 类型来存储总和。ret 变量用于累加所有学生的不满意度必须是 long long 类型否则会溢出。a 数组和 b 变量虽然 ai​ 和 bj​ 的值最大 106用 int 也能存但将它们定义为 long long 有以下好处统一数据类型避免在计算 abs(a[pos] - b) 时出现类型不匹配的问题。提高代码的兼容性即使未来题目数据范围扩大也无需修改类型定义。防止在极端情况下如 ai​ 和 bj​ 接近 106差值计算时出现溢出。结语