二分

C 中二分的代码，其实都差不多，就判断条件和变化内容不一样。这里有9道题目等你挑战！

二分

• 5.线段上点的个数
  • 题目：给你坐标轴X轴上的n个点, 以及q条线段, 对于每条线段你需要判断线段上有多少个点.
  • 输入输出描述：第一行输入一个整数T (T≤5), 表示数据组数 接下来T 组数据, 每组数据第一行输入两个整数n,q(1≤n≤10^5,1≤q≤50000) 第二行输入n 个整数ai(0≤ai≤10^80), 保证输入的数递增且互不相同 接下来q行每行输入两个整数ak,bk(0≤ak≤bk≤10^80) 表示一条线段
  • 样例： 输入： 1 5 3 1 4 6 8 10 0 5 6 10 7 100000 输出： Case 1: 2 3 2
  • 思路：定义两个函数，来寻找左端点和右端点。使用二分，避免超时。
  • 代码演示： #include <bits/stdc++.h> using namespace std; const int N = 100010; int a[N]; int t,n,q; int findleft(int num) //寻找左端点 { if (a[n] < num) return -1; int l = 1,r = n,best = -1; while (l <= r) { int mid = (l + r) / 2; if (a[mid] >= num) //没有出界时 { best = mid; r = mid - 1; } else { l = mid + 1; } } return best; } int flndright(int num) //寻找右端点 { if (a[1] > num) return -1; int l = 1,r = n,best = -1; while (l <= r) { int mid = (l + r) / 2; if (a[mid] <= num) //没有出界时 { best = mid; l = mid + 1; } else { r = mid - 1; } } return best; } int main() { int ca = 1; scanf("%d",&t); while (t--) { int x,y; scanf("%d%d",&n,&q); printf("Case %d:\n",ca); ca++; for (int i = 1;i <= n;i++) scanf("%d",&a[i]); while (q--) //二分 { scanf("%d%d",&x,&y); int l = findleft(x); //获取左端点 int r = flndright(y); //获取右端点 if (l == -1 || r == -1 || l > r) { printf("0\n"); //输出 } else { printf("%d\n",r - l + 1); //输出 } } } return 0; }
• 6.离散化
  • 题目：给你n个数，输出这n个数离散化后的结果 比如 4 100 80 10000 离散化后为 1 3 2 4 每个数的值为在原先数组中大小的排名,相同排名输出相同。 如1 1000 100 100 输出1 4 2 2
  • 输入输出描述： 输入： 第一行输入一个整数n 第二行输入n个整数ai 输出： 输出一行，包含n个正整数
  • 样例： 输入： 4 4 100 80 10000 输出： 1 3 2 4
  • 思路：复制输入的数组，比较a数组里的一个数，相对于b数组排第几。用一个函数来计算。
  • 代码演示： #include <bits/stdc++.h> using namespace std; const int N = 100010; int a[N],b[N]; int ans[N]; int find1(int num[],int n,int x) { //二分离散化 int l = 1,r = n,best = -1; while (l <= r) { int mid = (l + r) / 2; if (num[mid] >= x) { best = mid; r = mid - 1; }else l = mid + 1; } return best; } int main() { int n; scanf("%d",&n); for (int i = 1;i <= n;i++) { scanf("%d",&a[i]); b[i] = a[i]; //复制a数组 } sort(b + 1,b + n + 1); //注意要排序 for (int i = 1;i <= n;i++) printf("%d ",find1(b,n,a[i])); return 0; }
• 7.三角形的个数
  • 题目：给你N根长度不一样的木棍, 求这些木棍有多少种方法能凑成一个三角形
  • 输入输出描述： 输入： 第一行输入一个整数T(T≤10)表示数据组数 每组数据第一行输入一个整数N (3≤N≤2000), 接下来一行输入N个整数表示木棍长度,数据范围在[1, 10^9]之间 输出：对于每组数据输出一个整数
  • 样例： 输入： 3 5 3 12 5 4 9 6 1 2 3 4 5 6 4 100 211 212 121 输出： Case 1: 3 Case 2: 7 Case 3: 4
  • 思路：这次可以直接在循环里写二分，二分题目代码都差不多，写二分是有框架的。
  • 代码演示： #include <bits/stdc++.h> using namespace std; const int N = 100010; int a[N]; int main() { int t,ca = 0; scanf("%d",&t); while (t--) { long long ans = 0; printf("Case %d: ",++ca); int n; scanf("%d",&n); for (int i = 0;i < n;i++) scanf("%d",&a[i]); sort(a,a + n); for (int i = 0;i < n;i++) { for (int j = i + 1;j < n;j++) { //在循环里写二分 int l = j + 1,r = n - 1,best = -1; while (l <= r) { int mid = (l + r) / 2; if (a[i] + a[j] > a[mid]) { best = mid; l = mid + 1; } else r = mid - 1; } if (best != -1) { //如果best找到了 ans += best - j; //赋值 } } } printf("%lld\n",ans); //要转成long long类型 } return 0; }
• 8.开会
  • 题目：在x轴上有n个人，每个人有一个移动速度 v1,v2,v3...vn, 现在需要找一个地方让大家聚到一起开会，问你最少需要多少时间才可以让所有人都到达同一个点
  • 输入输出描述： 输入： 第一行输入一个整数n 第二行输入n个整数 x1,x2,x3...xn 表示每个人初始的位置 第三行输入n个整数 v1,v2,v3...vn表示每个人的移动速度 输出： 输出一个浮点数，保留五位小数
  • 样例1： 输入： 3 7 1 3 1 2 1 输出：2.00000 样例2： 输入： 10 2 3 5 7 11 13 17 19 23 29 6 5 4 3 2 1 2 3 4 5 输出： 2.75000
  • 思路：一样的，还是使用二分。注意变量是double类型的。
  • 代码演示： #include <bits/stdc++.h> using namespace std; const double eps = 1e-6; const int N = 100010; int n; int x[N],v[N]; bool judge(double mid) { //注意mid是double类型 double mi = -1e18; //变量都是double类型 double mx = 1e18; for (int i = 1;i <= n;i++) { double l = 1.0 * x[i] - v[i] * mid; double r = 1.0 * x[i] + v[i] * mid; if (l - mi > eps) mi = l; if (r - mx < -eps) mx = r; } if (mx - mi >= -eps) { //如果是正数 return true; } return false; } int main() { scanf("%d",&n); for (int i = 1;i <= n;i++) scanf("%d",&x[i]); for (int i = 1;i <= n;i++) scanf("%d",&v[i]); double l = 0,r = 1e9,best; int step = 50; while (step--) { //二分 double mid = (l + r) / 2; if (judge(mid)) { best = mid; r = mid; } else l = mid; } printf("%.5f\n",best); return 0; }
• 9.牛舍
  • 题目：农夫约翰搭了一间有N间牛舍的小屋。牛舍排在一条线上，第i号牛舍在xi的位置.但是他的M头牛对小屋很不满意，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其他牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。
  • 输入输出描述： 输入： 第一行输入2个整数N，M 第二行输入N个整数xi 输出： 输出一个整数，最大的最近距离
  • 样例： 输入： 5 3 1 2 8 4 9 输出： 3
  • 思路：用一个判断函数来判断怎么变化，二分的代码就不用说了。
  • 代码演示： #include <bits/stdc++.h> using namespace std; const int N = 100010; int n,m,a[N]; bool judge(int mid) { //判断函数 int pre = a[1]; int cnt = 1; for (int i = 2;i <= n;i++) { if (a[i] - pre >= mid) { //如果a[i]比pre还大mid pre = a[i]; //pre改变 cnt++; //计数器加一 } } return cnt >= m; } int main() { scanf("%d%d",&n,&m); for (int i = 1;i <= n;i++) scanf("%d",&a[i]); sort(a,a+n); int l = 1,r = (int)1e9,best = -1; while (l <= r) { //二分 int mid = (l + r) / 2; if (judge(mid)) { best = mid; l = mid + 1; } else r = mid - 1; } printf("%d",best); return 0; }
• 4.结尾0的个数
  • 题目：找到一个最小的N, 使得1×2×3...×N的末尾恰好有Q个0
  • 输入输出描述： 输入：第一行输入一个整数T, 接下来T行每行输入一个整Q T≤10000,1≤Q≤10^8 输出： 对于每组数据, 如果有解输出N的值, 否则输出'impossible', 具体格式见样例输出
  • 样例： 输入： 3 1 2 5 输出： Case 1: 5 Case 2: 10 Case 3: impossible
  • 思路：定义一个函数来计算5的个数，我们使用二分，这样会避免超时。最后如果找得到，就输出，找不到，输出impossible.
  • 代码演示： #include <bits/stdc++.h> using namespace std; int calc(int n) //计算5的个数 { int ret = 0; while (n > 0) { ret += n / 5; n /= 5; } return ret; } int main() { int n,a,ca = 1; scanf("%d",&n); while (n--) //while循环二分 { scanf("%d",&a); int l = 1,r = 1e9,best = -1; while (l <= r) { int mid = (l + r) / 2; if (calc(mid) >= a) { best = mid; r = mid - 1; } else { l = mid + 1; } } //以上为二分常写的代码 if (calc(best) == a) //找得到 { printf("Case %d: %d\n",ca++,best); } else //找不到 { printf("Case %d: impossible\n",ca++); } } return 0; }
• 3.lowerbound与upperbound
  • 题目：给你一个有序的整数序列，有一系列的询问，每次询问给出一个整数num,你需要回答序列中第一个等于num的位置，最后一个等于num的位置，第一个大于num的位置,如果相应的位置不存在，就输出-1.
  • 输入输出描述： 输入： 第一行输入一个整数n (1<=n<=100000) 第二行输入n个整数ai, (1<=ai<=100000) 第三行输入一个整数m,表示询问的个数 (1<=m<=100000) 接下来m行每行一个整数bi,(0<=bi<=100000) 输出：对于每个询问输出三个整数
  • 样例： 输入： 10 1 3 5 7 7 7 7 9 10 11 6 1 0 7 8 11 12 输出： 1 1 2 -1 -1 1 4 7 8 -1 -1 8 10 10 -1 -1 -1 -1
  • 思路：写三个函数来查找位置，第一个是正序枚举，第二个是倒序，第三个可以直接返回best的值，二分的代码都差不多，只要记住格式就行了。
  • 代码演示： #include <bits/stdc++.h> using namespace std; const int N = 100010; int n,a[N]; int find1(int x){ //寻找出现第一次的位置 int l = 1,r = n,best = -1; while (l <= r){ int mid = (l + r) / 2; if (a[mid] >= x){ best = mid; r = mid - 1; }else l = mid + 1; } //代码差不多 if (best == -1) return -1; if (a[best] == x) return best; return -1; } int find2(int x){ //寻找最后一次的位置 if (a[1] > x || a[n] < x) return -1; int l = 1,r = n,best = n + 1; while (l <= r){ int mid = (l + r) / 2; if (a[mid] > x){ r = mid - 1; best = mid; }else l = mid + 1; } //代码差不多 best--; if (a[best] == x) return best; return -1; } int find3(int x){ //寻找比输入数大的第一个数的位置 int l = 1,r = n,best = -1; while (l <= r){ int mid = (l + r) / 2; if (a[mid] > x){ r = mid - 1; best = mid; }else l = mid + 1; } //代码差不多 return best; } int main() { int m; int x; scanf("%d",&n); for (int i = 1;i <= n;i++) scanf("%d",&a[i]); scanf("%d",&m); while (m--){ scanf("%d",&x); printf("%d %d %d\n",find1(x),find2(x),find3(x)); //输出三个数所在的位置 } return 0; }
• 2.快速幂
  • 题目：求 a^b mod p ，其中p=1e9+7 。
  • 输入输出描述： 输入：输入一行，两个整数a和b。 输出：输出a^b mod p 的结果。
  • 样例1：输入：2 3 输出：8 样例2：输入：3 100000 输出：916902199
  • 思路：需要把答案转化成long long类型，如果b是1就直接返回a.奇数和偶数是有区分的。定义一个int变量，用来做二分。然后返回long long类型取余之后的值。
  • 代码演示： #include <bits/stdc++.h> using namespace std; const int p = (int)1e9 + 7; //注意要转换成int类型 int mypow(int a,int b) //计算a的b次方 { if (b == 1) //如果是一次 { return a; //返回a } if (b % 2 == 1) //如果是奇数 { int x = mypow(a,b/2); return 1LL * a * x % p * x % p; //这里要注意变成long long类型 //要多乘一个a //因为b是奇数 } else { int x = mypow(a,b/2); return 1LL * x * x % p; } } int main() { int a,b; cin >> a >> b; cout << mypow(a,b); //调用二分 return 0; }
• 1.有序数组中某个数的位置
  • 题目：在一个有序数组中，查找x所在的下标。
  • 输入输出描述： 输入： 第一行两个整数n和m。 第二行n个数，表示有序的数列。 接下来m行，每行一个整数x，表示一个询问的数。 输出： 对于每个询问如果x在数列中，输出下标。否则输出-1
  • 样例： 输入： 5 3 3 4 5 7 9 7 3 8 输出： 4 1 -1
  • 思路：如果直接遍历，肯定会超时。那么就要使用二分，二分的代码都差不多，所以不做讲解了。
  • 代码演示： #include <bits/stdc++.h> using namespace std; const int N = 100010; int a[N]; int n; int find(int l,int r,int x) { if (l > r) return -1; //如果数组为空 if (l == r) { if (a[l] == x) return l; //如果只有一个 else return -1; } int mid = (l + r) / 2; //二分 if (a[mid] == x) return mid; if (a[mid] > x) return find(l,mid-1,x); return find(mid+1,r,x); } int main() { int m,x; scanf("%d%d",&n,&m); for (int i = 1;i <= n;i++) { scanf("%d",&a[i]); } while (m--) { scanf("%d",&x); int ret = find(1,n,x); printf("%d\n",ret); } return 0; }