ACM.二分查找 客官°小女子只卖身不卖艺 2023-06-29 07:27 9阅读 0赞 二分，分的是答案，直接在答案在的区间范围中二分，分出一个值，就判断是不是答案，并进行转移 如果已知候选答案的范围（min,max）（单调有序），有时候我们不必通过计算得到答案，只需在此范围内应用“二分”的过程，逐渐靠近答案（最后，得到答案）！ 通过二分的方法，大幅度地跳过一片没必要的比较和选择。 一.二分查找 二分法求零点，把区间折半来找零点，虽然找不到具体的零点值但是可以确定大体零点的一个范围，达到一定精度后可以看作答案。 所以我们现在就是把这种思想转化为一个问题 即问题如下：给定一个有序的数组，查找k是否在数组中 分析：首先，将表中间位置记录的关键字与k比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子区间，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子区间，否则进一步查找后一子区间。 重复以上过程，直到找到满足条件的记录，使查找成功，或直到子区间不存在为止，此时查找不成功．容易知道算法的时间复杂度为O（logN）。 一.NEFU-956 二分查找 Problem:A Time Limit:1000ms Memory Limit:65536K Description 有n(1<=n<=1000005)个整数，已经按照从小到大顺序排列好，现在另外给一个整数x，请找出序列中第1个大于x的数的下标！ Input 输入数据包含多个测试实例，每组数据由两行组成，第一行是n和x，第二行是已经有序的n个整数的数列。 Output 对于每个测试实例，请找出序列中第1个大于x的数的下标！。 Sample Input 3 3 1 2 4 Sample Output 2 #include <bits/stdc++.h> #include<algorithm> using namespace std; int a[1000007],n,x,i; int main() { while(scanf("%d%d",&n,&x)!=-1) { for(i=0;i<n;i++) { cin>>a[i]; } printf("%d\n",upper_bound(a,a+n,x)-a); } return 0; } upper\_bound函数指返回要找的值的下标。 二.NEFU-1646 小清新的二分查找之旅 Problem:B Time Limit:1000ms Memory Limit:65535K Description 小清新又在疯狂懵逼了，遇到了一道题，并且发誓绝对不会告诉别人：在题号899的题目上脸懵逼了好久，于是他决定强化一下题目900，以抒发心中的抑郁之气。所以…… 给出一组整数，整数个数为n，n不超过1,000,000，问这组整数中是否有k，总共询问q次。 Input 多组输入。 每组输入输入： 第一行2个整数：n q ，1 <=q , n <= 1,000,000 。 第二行 有 n 个整数，已升序排序。所有数 <= 1 e 9+7. 第三行 有 q 个整数，用于查询。 每行各数据之间有空格隔开。 Output 对每个查询数据分别输出一行 存在输出： no 不存在输出： YES Sample Input 5 2 1 2 3 4 5 2 10 Sample Output no YES 二分查找的模板题 三.函数的零点问题 NEFU-1645 小清新的函数坐标-二分 Problem:C Time Limit:1000ms Memory Limit:65535K Description 一天，小清新用一些奇奇怪怪的工具绘制函数图像，玩得不亦乐乎，期间发现了一个函数： F(x) = 0.0001 x^5 + 0.003 x^3 + 0.5 x - 3 ，聪明的他一眼see穿了它的单调性，现在，小清新想标注一些点，已经写出了它们的 y 坐标值 ，聪明的你能帮助 可爱善良的小清新把对应的 x 坐标值找出来么。谢谢啦！ 保证： -20 < x < 20 。答案精确到小数点后第4位。数据多组输入形式。 Input （多组输入）每行一个实数 y Output 每行一个四位小数 x Sample Input \-356.957952 350.957952 Sample Output \-19.9995 19.9995 #include <bits/stdc++.h> #include<algorithm> using namespace std; double y,l,r,mid; double fun(double x) { double m; m=0.0001*x*x*x*x*x+0.003*x*x*x+0.5*x-3; return m; } int main() { while(scanf("%lf",&y)!=-1) { l=-20.0; r=20.0; while(l<r) { if(r-l<1e-5)break; mid=(l+r)/2.0; if(fun(mid)>y) //因为是单调递增函数。 r=mid; else l=mid; } printf("%.4lf\n",mid); } return 0; } 小清新的二倍问题加强版-二分-桶排 Problem:D Time Limit:2000ms Memory Limit:65535K Description 小清新又要使坏了，他发现二倍问题（Problem 8）并不能难住大家，于是他决定悄咪咪的改一波数据。 于是： 给定2到10,000个不同的正整数，你的任务是计算这些数里面有多少个数对满足：数对中一个数是另一个数的两倍。比如给定1 4 3 2 9 7 18 22，得到的答案是3，因为2是1的两倍，4是2个两倍，18是9的两倍。 Input 输入包括n组测试数据。第一行一个正整数 n 。 接下来n行表示n组数据，每组数据为一行，给出2到10,000个两两不同且小于100,000的正整数。每一行最后一个数是0，表示这一行的结束后，这个数不属于那2到10,000个给定的正整数。 Output 对每组输入数据，输出一行，给出有多少个数对满足其中一个数是另一个数的两倍。 Sample Input 3 1 4 3 2 9 7 18 22 0 2 4 8 10 0 7 5 11 13 1 3 0 Sample Output 3 2 0 可以用桶排序解决 #include <bits/stdc++.h> #include<algorithm> using namespace std; int a[100001],n,i,j,b[10001]; int main() { cin>>n; while(n--) { memset(a,0,sizeof(a)); int t,sum=0; for(j=0;j<10001;j++) { cin>>b[j]; a[b[j]]++; if(b[j]==0)break; } for(j=1;j<50000;j++) { if(a[j]>=1&&a[j*2]>=1)sum++; } printf("%d\n",sum); } return 0; } 简单几何-二分 Problem:1303 Time Limit:1000ms Memory Limit:65535K Description 一个长方体体积为v1，长为r，高为h，宽为1。一个圆柱体体积为v2，底面半径为r，高为h。r的取值范围为0<r<=100000,h的取值范围为1<=h<=100000的整数。给出h求使v2与v1的差值小于等于r^π的r的最小值 Input 输入第一行为一个整数t，表示接下来有t组数据。第二行到第t+1行，每行一个整数表示h Output 输出r并保留4位小数 Sample Input 4 1 2 3 4 Sample Output 2.4073 4.7047 6.8441 8.8921 #include <bits/stdc++.h> using namespace std; const double pai=acos(-1.0); double ans; int h; int judge(double r) { if(pow(r,pai)>=h*(pai*r*r-r))return 1; else return 0; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d",&h); double l=0,r=100000; int i=0; double mid; while(l<r) { mid=(l+r)/2.0; if(r-l<=1e-8)break; if(judge(mid)) { ans=mid; r=mid;} else { l=mid; } } printf("%.4lf\n",ans); } return 0; } NEFU-1648 小清新切绳子-二分 Problem:F Time Limit:1000ms Memory Limit:65535K Description 小清新又双叒叕被WA疯了，原来是被double类型的精度给坑了，但题目那么好，怎么能不安利一波呢=。= 于是他悄悄地修改了下数据，安利给那些可爱的小可爱们（没错(￣▽￣)~\*），就是屏幕前的你们。 有N条绳子，它们的长度分别为Li。如果从它们中切割出K条长度相同的绳子，这K条绳子每条最长能有多长？ Input 多组输入！ 第一行两个整数N和K，接下来一行N个整数，描述了每条绳子的长度Li ，以空格隔开。 对于100%的数据 1<=Li<10,000,000 ， 1<=n，k<=10000 Output 切割后每条绳子的最大长度（一个整数） Sample Input 4 11 802 743 457 539 Sample Output 200 用二分法找到一个值，判断是否是合理的值，然后根据精度要求输出。 #include <bits/stdc++.h> using namespace std; int i,j,n,k,ans; int a[10000]; int pan(int a[],int d) { long long sum=0; for(i=0;i<n;i++) { sum+=(a[i]/d); //看输入的总段数能否由给定的绳子长度制造出 } if(sum>=k)return 1; else return 0; } int main() { ios::sync_with_stdio(0); while(cin>>n>>k) { ans=0; int a[n],m=-99999999; for(i=0;i<n;i++) { cin>>a[i]; if(a[i]>m)m=a[i]; } int mid,l=0,r=m; while(l<=r) { mid=(l+r)/2; if(pan(a,mid)) { ans=mid; l=mid+1; } else { r=mid-1;} } cout<<ans<<endl; } return 0; } 切绳子实数版-二分 Problem:H Time Limit:1000ms Memory Limit:65535K Description 有N条绳子，它们的长度分别为Li。如果从它们中切割出K条长度相同的 绳子，这K条绳子每条最长能有多长？答案保留到小数点后2位。 Input 第一行两个整数N和K，接下来N行，描述了每条绳子的长度Li。 Output 切割后每条绳子的最大长度。 Sample Input 4 11 8.02 7.43 4.57 5.39 Sample Output 2.00 将所给的数字\*100转为整数即可 #include <bits/stdc++.h> using namespace std; int i,j,n,k,ans; double ansq; int pan(int b[],int d) { long long sum=0; for(i=0;i<n;i++) { sum+=int(b[i]/d); } if(sum>=k)return 1; else return 0; } int main() { while(scanf("%d%d",&n,&k)!=-1) { ans=0; double a[n],m=-99999999; int b[n]; for(i=0;i<n;i++) { scanf("%lf",&a[i]); b[i]=int(a[i]*100); if(b[i]>m)m=b[i]; } int mid,l=0,r=m; while(l<=r) { mid=(l+r)/2.0; if(mid==0)break; if(pan(b,mid)) { ans=mid; l=mid+1; } else { r=mid-1;} } ansq=double(ans/100.0); printf("%.2lf\n",ansq); } return 0; } 卖古董-DP-二分 Problem:G Time Limit:1000ms Memory Limit:65535K Description 你的朋友小明有n个古董，每个古董的价值给出，然后小明要在接下来的m天内将所有古董依次卖出（注意：必须依次卖出，也就是从第一个开始卖卖到最后一个），小明希望 的是这m天内每天卖出的价值和的最大值最小，你来帮助他把？ Input 一共T组数据，每组一个n和m，代表n个古董以及m天（1<=m<=n）,然后下面n行为古董的价值,古董价值为1到10000（1<=n<=100000） Output 输出m天内卖出的古董价值和的最大值（当然是最优的时候），我们希望的是这个最大值越小越好 Sample Input 3 7 5 100 400 300 100 500 101 400 4 3 2 6 2 4 4 2 2 6 2 4 Sample Output 500 6 8 与切绳子问题相似， #include <bits/stdc++.h> using namespace std; int T,m,n,i,j,sum,ans; int check(int mid,int m,int a[]) { int num=0,s=0; for(int j=0;j<n;j++) { s+=a[j]; if(s>mid){ num++; //判断二分测试的值是否合理 s=a[j];} } if(num<m)return 1; else return 0; } int main() { scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); int a[n]; sum=0; int max1=0; for(i=0;i<n;i++) { scanf("%d",&a[i]); sum+=a[i]; max1=max(max1,a[i]); } int l,r,mid; l=max1;r=sum; while(l<=r) { mid=l+(r-l)/2; if(check(mid,m,a))r=mid-1; else { l=mid+1; } } printf("%d\n",l); } return 0; } 数列分段-二分 Problem:I Time Limit:1000ms Memory Limit:65535K Description 对于给定的一个长度为N的正整数数列A-i，现要将其分成M(M≤N)段，并要求每段连续，且每段和的最大值最小。 关于最大值最小： 例如一数列4 2 4 5 1要分成3段 将其如下分段： \[4 2\]\[4 5\]\[1\] 第一段和为6，第2段和为9，第3段和为1，和最大值为9。 将其如下分段： \[4\]\[2 4\]\[5 1\] 第一段和为4，第22段和为6，第33段和为6，和最大值为6。 并且无论如何分段，最大值不会小于6。 所以可以得到要将数列4 2 4 5 1要分成3段，每段和的最大值最小为6。 Input 第11行包含两个正整数N，M。 第22行包含N个空格隔开的非负整数A\_i 含义如题目所述。 Output 一个正整数，即每段和最大值最小为多少。 Sample Input 5 3 4 2 4 5 1 Sample Output 6 本质与上一道题一样，都是求一种分段方法，使所有段中的最大值最小的问题 #include <bits/stdc++.h> using namespace std; int T,m,n,i,j,sum,ans; int check(int mid,int m,int a[]) { int num=0,s=0; for(int j=0;j<n;j++) { s+=a[j]; if(s>mid){ num++; s=a[j];} } if(num<m)return 1; else return 0; } int main() { scanf("%d%d",&n,&m); int a[n]; sum=0; int max1=0; for(i=0;i<n;i++) { scanf("%d",&a[i]); sum+=a[i]; max1=max(max1,a[i]); } int l,r,mid; l=max1;r=sum; while(l<=r) { mid=l+(r-l)/2; if(check(mid,m,a))r=mid-1; else { l=mid+1; } } printf("%d\n",l); return 0; }
相关 ACM.二分查找 二分，分的是答案，直接在答案在的区间范围中二分，分出一个值，就判断是不是答案，并进行转移 如果已知候选答案的范围（min,max）（单调有序），有时候我们不必通过计算得到答 客官°小女子只卖身不卖艺/ 2023年06月29日 07:27/ 0 赞/ 9 阅读
相关 二分查找 二分查找可以说是在经典不过的查找算法了，比如JAVA的库函数里，就有相应的代码实例。如下写出两个版本的二分查找，非递归和递归的 非递归的 public int bi 系统管理员/ 2022年08月06日 16:24/ 0 赞/ 90 阅读
相关 二分查找 //二分查找 /\ 递归算法 int searchB1(int A\[\], int low, int high, int data); 非递归算法 int 绝地灬酷狼/ 2022年05月12日 01:40/ 0 赞/ 83 阅读
相关 查找——二分查找 基本思想 二分查找是建立在有序顺序表基础上的！步骤如下： 1. 将表中间位置记录的关键字与给定K值进行比较，若两者相等，则查找成功。 2. 蔚落/ 2022年03月27日 03:46/ 0 赞/ 429 阅读
相关 二分查找 二分查找（先排序） typedef struct LNode List; struct LNode{ ElemenType Data[MAXSIZ 爱被打了一巴掌/ 2022年02月02日 17:13/ 0 赞/ 161 阅读
相关 二分查找 使用递归的版本 def bin_search(lst, num, start=None, end=None): """ 二分查找 àì夳堔傛蜴生んèń/ 2022年01月07日 04:03/ 0 赞/ 139 阅读
相关 二分查找 int search2( int array\[\], int n, int v) \{ int left, right, middle; 心已赠人/ 2021年12月20日 16:07/ 0 赞/ 165 阅读
相关 二分查找 二分查找 二分查找是一个比较简单的算法，用 C++ 语言实现如下： template <typename T> int binary_search( ゞ 浴缸里的玫瑰/ 2021年12月13日 03:57/ 0 赞/ 233 阅读
相关 二分查找 > 一、自己实现的 include<iostream> include<cstdio> include<algorithm> u 左手的ㄟ右手/ 2021年09月21日 17:12/ 0 赞/ 332 阅读
客官°小女子只卖身不卖艺
系统管理员
爱被打了一巴掌
àì夳堔傛蜴生んèń
ゞ 浴缸里的玫瑰
左手的ㄟ右手
还没有评论，来说两句吧...