acm新手小白必看系列之（8）——二分法精讲及例题

老翟笔记今日分享的是:acm新手小白必看系列之（8）——二分法精讲及例题

acm新手小白必看系列之（8）——二分法精讲及例题 二分，分的是答案，直接在答案在的区间范围中二分，分出一个值，就判断是不是答案，并进行转移 如果已知候选答案的范围（min,max）（单调有序），（无序的话自己排序），有时候我们不必通过计算得到答案，只需在此范围内应用“二分”的过程，逐渐靠近答案（最后，得到答案）！ 通过二分的方法，大幅度地跳过一片没必要的比较和选择 首先介绍最典型的二分——二分查找 二分法求零点，把区间折半来找零点，虽然找不到具体的零点值但是可以确定大体零点的一个范围，达到一定精度后可以看作答案。 所以我们现在就是把这种思想转化为一个问题 即问题如下：给定一个有序的数组，查找k是否在数组中 分析：首先，将表中间位置记录的关键字与k比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子区间，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子区间，否则进一步查找后一子区间。 重复以上过程，直到找到满足条件的记录，使查找成功，或直到子区间不存在为止，此时查找不成功．容易知道算法的时间复杂度为O（logN） 实例1 实例2 如果还是使用 for 循环查找的话 很显然，一般也要比较到最后才会发现不存在 用二分查找，便可以在过程中，大片大片地省去检查那些没有必要的“可能答案” 随着数据量的提升，复杂度也稳定于O(Log n) 实例3 （加inline是内联函数的意思，这又是啥意思呢，可以理解为有的时候加上去之后可以加快运行速度。） 显然可以用上图的函数来做，用二分法怎么做呢？ 第一种 ——循环 第二种——递归 1.二分查找upper_bound 有n(1<=n<=1000005)个整数，已经按照从小到大顺序排列好，现在另外给一个整数x，请找出序列中第1个大于x的数的下标！ Input 输入数据包含多个测试实例，每组数据由两行组成，第一行是n和x，第二行是已经有序的n个整数的数列。 Output 对于每个测试实例，请找出序列中第1个大于x的数的下标。 Sample Input 3 3 1 2 4 Sample Output 2 Hint 本题为多组数据，while(scanf("%d%d",&n,&m)!=-1)即可 #include <bits/stdc++.h> using namespace std; const int N=2E6+9; int a[N]; int main() { int n,x,ans;while(~scanf("%d%d",&n,&x)){ for(int i=1; i<=n; i++){ scanf("%d",&a[i]);}int ans=upper_bound(a,a+n,x)-a;// //lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址， //不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。 //upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址， //不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。cout <<ans-1<< endl;}return 0; } 2.二分查找例题 给出一组整数，整数个数为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 #include <bits/stdc++.h> using namespace std; int n,q,k,i,l,r,m,a[1000010]; bool judge(int l,int r,int cmp) { while(l<=r){ m=l+(r-l)/2;//二分if(a[m]>cmp) r=m-1;if(a[m]<cmp) l=m+1;if(a[m]==cmp) return 1;}return 0; } int main() { ios::sync_with_stdio(false);//取消关联，详解看往期while(cin>>n>>q){ for(i=1;i<=n;i++)cin>>a[i];while(q--){ cin>>k;if(judge(1,n,k))printf("no\n");elseprintf("YES\n");}}return 0; } 3.找坐标 一天，小蓝用一些奇奇怪怪的工具绘制函数图像，玩得不亦乐乎，期间发现了一个函数： 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> using namespace std; double y, x; double F(double t) { return 0.0001*pow(t, 5)+0.003*pow(t, 3)+0.5*t-3; } int main() { while(scanf("%lf", &x) != EOF){ double l=-20, r=20, mid;while(F(r)-F(l) >= 1e-5){ mid = (l+r)/2;//二分法 if(F(mid) > x) r=mid;else l=mid;}printf("%.4lf\n", mid);}return 0; } 4.倍数问题 给定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> using namespace std; int n,i,l,r,m,cnt,ans,a[10010]; bool seek(int l,int r,int cmp) { while(l<=r){ m=l+(r-l)/2;if(a[m]>cmp)r=m-1;if(a[m]<cmp)l=m+1;if(a[m]==cmp)return 1;}return 0; } int main() { ios::sync_with_stdio(false);cin>>n;while(n--){ ans=cnt=0;while(cin>>a[cnt]&&a[cnt])cnt++;sort(a,a+cnt);for(i=0;i<cnt;i++)ans=ans+seek(0,cnt-1,2*a[i]);printf("%d\n",ans);}return 0; } #include <bits/stdc++.h>//桶排思想 using namespace std; const int N=1e4+10,M=2e5+10; int t,x,n,ans,a[N],vis[M]; int main() { ios::sync_with_stdio(false);cin>>t;while(t--){ n=0;memset(vis,0,sizeof(vis));while(cin>>x&&x)vis[2*x]=1,a[++n]=x;ans=0;for(int i=1;i<=n;i++)if(vis[a[i]])ans++;printf("%d\n",ans);}return 0; } 5.进阶题目，切绳子 有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 #include <cstdio> #include <cmath>//换成万能头文件即可 using namespace std; const int M=10005;//于define用法类似但是有一些地方不同 const double inf=2000000002.0; double L[M]; int n,k; bool judge(double x) { int num=0;for(int i=0;i<n;i++)num+=(int)(L[i]/x);//强制转换return num>=k; } void solve()//一种神奇的用法 { double left=0,right=inf;for(int i=0;i<100;i++){ double mid=(left+right)/2;if(judge(mid)) left=mid;else right=mid;}printf("%.2f\n",floor(right*100)/100);//floor() 函数用于求不大于 x 的最大整数，也即向上取整。 } int main() { while(scanf("%d%d",&n,&k)!=-1){ for(int i=0;i<n;i++)scanf("%lf",&L[i]);solve();}return 0; } 练习往期回顾 .越狱 Description 　　监狱有连续编号为1…N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果 相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱 Input 输入两个整数M，N.1<=M<=10^8,1<=N<=10^12 Output 　　可能越狱的状态数，模100003取余 Sample Input 2 3 Sample Output 6 HINT 　　6种状态为(000)(001)(011)(100)(110)(111) #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm>//换成万能头文件 using namespace std; long long c=100003; long long pow_mod(long long a,long long b){ long long ans=1%c;a%=c;while(b){ if(b&1)ans=ans*a%c;b>>=1;a=a*a%c;}return ans; } int main(){ long long n,m;scanf("%lld%lld",&m,&n);long long x=pow_mod(m,n);long long y=m*pow_mod(m-1,n-1)%c;long long s=(x-y+c)%c;printf("%lld",s); } 本期练习 1.乱序排序 有n(1<=n<=2000005)个整数，是乱序的，现在另外给一个整数x，请找出序列排序后的第1个大于x的数的下标！ Input 输入数据包含多个测试实例，每组数据由两行组成，第一行是n和x，第二行是已经有序的n个整数的数列。 Output 对于每个测试实例，请找出从小到大排序后的序列中第1个大于x的数的下标！。 Sample Input 3 3 1 4 2 Sample Output 2 2.分段 对于给定的一个长度为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 Hint N≤100000,M≤N,A i之和小于1e9 *代码在下一期噢~~~~~* 下节提示 acm新手小白必看系列之（9）——栈精讲及例题

本文结束，感谢您的阅读和支持，希望以上内容能给你带来帮助。本文章来自网络，由老翟笔记小编团队整理发布。