备赛蓝桥杯之二分
-
-
梁老师 北京小升初老师～
0 人点赞了该文章 · 98 浏览
32 5 82105
85
https://www.dotcpp.com/oj/problem2926.html我第一眼看看就是简单的一个二分，然后就迅速写了一下就提交，结果才对了9分。
为什么错呢？我也百思不得其解。看看别人的题解不知道，为什么最后还要判断一下。后来又在网上搜了一下这个题，发现了一个重要的地方。那就是我读题不认真，需要求的是最接近的元素，自然需要进行判断。所以说，下次做题之前要认真读题！！！
来说说思路吧！
首先，咱们为了减少运行时间。把要查找的元素 x 进行一个划分，分为两大类，三小类。两大类是元素 x 是否在序列中。如果不在序列中，直接输出序列中最大/最小的元素即可；在序列中的时候再进行二分即可！如下分为三种情况。
要查找的元素 x 小于序列中的首元素。此时，首元素最接近 x ，输出首元素即可
要查找的元素 x 大于序列中的最后一个元素。此时。最后一个元素最接近 x，输出最后一个元素即可。
要查找的元素在序列里面，再进行二分操作。
当 | q[ l - 1] - x | < | q[ l ] - x | 时，表示 q[l - 1] 最接近 x ，输出 q[l-1]即可。 当 | q[ l - 1] - x | = | q[ l ] - x | 时，由于题目要求多个值满足时，输出最小值即可。所以输出 q[ l - 1 ] 即可。 当 | q[ l - 1] - x | > | q[ l ] - x | 时，表示 q[ l ] 最接近 x ,输出 q[ l ] 即可。
int l = 0,r = n - 1;while(l < r){int mid = (l + r) / 2;if(q[mid] >= x)r = mid;elsel = mid + 1;}
int l = 0,r = n - 1;while(l < r){int mid = (l + r + 1) / 2;if(q[mid] <= x)l = mid;elser = mid - 1;}
#include<iostream>#include <cmath>using namespace std;const int N = 1e5 + 10;int q[N],n,m;int main(){scanf("%d",&n);for(int i = 0;i < n;i++)scanf("%d",&q[i]);scanf("%d",&m);int x;while(m--){scanf("%d",&x);if(x <= q[0])printf("%d\n",q[0]);else if(x >= q[n - 1])printf("%d\n",q[n - 1]);else{int l = 0,r = n - 1;while(l < r){int mid = (l + r) / 2;if(q[mid] >= x)r = mid;elsel = mid + 1;}if(abs(q[l] - x) < abs(q[l - 1] - x))printf("%d\n",q[l]);elseprintf("%d\n",q[ l - 1]);}}return 0;}
#include<iostream>#include <cmath>using namespace std;const int N = 1e5 + 10;int q[N],n,m;int main(){scanf("%d",&n);for(int i = 0;i < n;i++)scanf("%d",&q[i]);scanf("%d",&m);int x;while(m--){scanf("%d",&x);if(x <= q[0])printf("%d\n",q[0]);else if(x >= q[n - 1])printf("%d\n",q[n - 1]);else{int l = 0,r = n - 1;while(l < r){int mid = (l + r + 1) / 2;if(q[mid] <= x)l = mid;elser = mid - 1;}if(abs(q[l] - x) <= abs(q[l + 1] - x))printf("%d\n",q[l]);elseprintf("%d\n",q[ l + 1]);}}return 0;}
https://blog.csdn.net/lq1990717/article/details/124441505其实也没有什么难的，有两个需要注意的点。
第一个是控制小数点的位数，while循环的条件是 r - l >1e-8。至于为什么请看之前的文章实数二分。
第二个是二分的条件。什么情况需要二分哪一个区间。对于这个求函数的零点，咱们需要知道一个定理就是零点存在定理。
https://baike.baidu.com/item/%E5%8B%98%E6%A0%B9%E5%AE%9A%E7%90%86?fromtitle=%E9%9B%B6%E7%82%B9%E5%AD%98%E5%9C%A8%E5%AE%9A%E7%90%86&fromid=23707175&fromModule=lemma_search-box内容：函数在一个区间（a，b）上连续，且 f(a) * f(b) < 0，表明这个区间一定存在一个零点！
#include <iostream>#include <cmath>using namespace std;double function(double x){return pow(x,5) - 15 * pow(x,4) + 85 * pow(x,3 ) - 225 * pow(x,2) + 274 * x - 121;}int main(){double l = 1.5,r = 2.4;while(r - l > 1e-8){double mid = (l + r) / 2;if(function(l) * function(mid) < 0)// 表明[l,mid]存在零点r = mid;// 更新区间方式else// 否则[mid,r]里面存在零点l = mid;}printf("%lf\n",l);return 0;}
添加 家长论坛微信
全部 0条评论