二分

二分模板 1.二分模板二分的本质并不是单调性，而是一种边界。 定义某种性质，使得右半边的部分全部满足该种性质，而左半边的部分全部都不满足该种性质。而二分可以寻找性质的边界。 12345678910111213141516171819//区间[low, high]被划分成[low, mid - 1]和[mid, high]时使用:while (low < high) { int mid = low + high + 1 >> 1; if (check(mid)) low = mid; else high = mid - 1;}//区间[low, high]被划分成[low, mid]和[mid + 1, high]时使用:while (low < high) { int mid = low + high >> 1; if (check(mid)) high = mid;//check判断mid是否满足性质 else low = mid + 1;}//小数二分const double eps = 1e-6;//eps表示精度 取决于题目对精度的要求while (high - low > 1e-8) { double mid = (low + high) / 2; if (check(mid)) low = mid; else high = mid;} 1.AcWing789.数的范围 123456789101112131415161718192021222324252627282930313233343536373839#include<iostream>using namespace std;const int MAX = 1e6 + 10;int n, m, arr[MAX];//整数二分模板//思路：对数组进行二分 分别查找某个数字出现范围的起始坐标与终止坐标int main() { scanf("%d %d", &n, &m); for (int i = 0; i < n; ++i) scanf("%d", ...

第一个错误的版本 原题链接：https://leetcode.cn/problems/first-bad-version/ 你是产品经理，目前正在带领一个团队开发新的产品。 不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。 假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。 你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。 实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。 1.二分答案01123456789101112131415class Solution {public: int firstBadVersion(int n) { long long l = 1, r = n; while (l != r) { long long mid = (l + r) /2; if (isBadVersion(mid)) { r = mid; } else { l = mid + 1; } } return l; }};

x的平方根 原题链接：https://leetcode.cn/problems/sqrtx/ 给你一个非负整数 x ，计算并返回 x 的 算术平方根。 由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。 注：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。 1.二分答案10123456789101112131415class Solution {public: int mySqrt(int x) { long long l = 0, r = x; while (l != r) { long long mid = (r + l + 1) / 2; if (mid * mid <= x) { l = mid; } else { r = mid - 1; } } return r; }};

搜索插入位置 原题链接：https://leetcode.cn/problems/search-insert-position/ 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 1.暴力法123456789class Solution {public: int searchInsert(vector<int>& nums, int target) { for (int i = 0; i < nums.size(); ++i) { if (nums[i] >= target) return i; } return nums.size(); }}; 2.二分查找12345678910111213141516class Solution {public: int searchInsert(vector<int>& nums, int target) { if (nums[nums.size() - 1] < target) return nums.size(); int l = 0, r = nums.size() - 1; while (l != r) { int mid = (l + r) / 2; if (nums[mid] >= target) { r = mid; } else { l = mid + 1; } } return l; }};

伐木 原题链接：http://oj.haizeix.com/problem/82 又到了伐木的季节，亚布力林业局引进了一台新的伐木设备： 这种设备能设定一个高度值（整数），并将所有树木大于此高度的部分锯下来。 例如，有四棵树的高度分别为20M、17M、15M、10M，把设备的高度设定为 15M，那么设备运行过后树的高度变为15M、15M、15M、10M（从第一棵树锯下 5M，从第二棵树锯下 2M，总共锯下 7M）。 现在林业局需要至少锯下长度为M米的木头，因为国家推行的环保政策，林业局不能锯下过多的木材。 需要将伐木设备的高度设定为多少才能使得获得的木材至少为 M 米？ 换句话说，如果再将高度升高一米，将得不到 M 米的木材，如果将高度减少一米，将不能通过环保政策。 输入： 第一行两个整数 N 和 M，N 表示树木的数量，M 表示需要木材的长度。（1 ≤ N ≤ 1000000 , 1 ≤ M ≤ 2000000000） 第二行 N 个整数表示每棵树的高度（N ≤ 1000000000）。所有数据必有解。 输出： 一个整数，表示伐木的最高高度。 样例： 124 920 17 15 10 114 1.思路 根据设定伐木设备的设定长度num[i]，利用fun()函数进行计算，能求出其能够获得的伐木量 根据当前能够获取的伐木量s与题目给定真实需要的伐木量m进行比较，从而调整左右指针 当左右指针逼近到一定范围时，表示最佳答案已经找到 2.代码实现1234567891011121314151617181920212223242526272829303132333435363738#include<iostream>using namespace std;long long n, m, num[1000005], rawr;long long func(long long x) { long long t = 0; for (int i = 0; i < n; ++i) { if (num[i] > x) { t += num[i] - x; } } return t;}long long bs() { ...

数列分段 原题链接：http://oj.haizeix.com/problem/391 对于给定的一个长度为 N 的正整数数列 Ai ，现要将其分成 M（M ≤ N）段，并要求每段连续、且每段和的最大值最小。 关于最大值最小： 例如一数列 4 2 4 5 1 要分成 3 段， 将其如下分段：[4 2] [4 5] [1]：第1段和为 6、第 2 段和为 9、第 3 段和为 1，和最大值为 9。 将其如下分段：[4] [2 4] [5 1]：第1段和为 4、第 2 段和为 6、第 3 段和为 6，和最大值为 6。 并且无论如何分段，最大值不会小于 6。 所以可以得到，要将数列 4 2 4 5 1 分成 3 段，每段和的最大值最小为 6。 输入： 第一行两个整数 N , M。（1 ≤ M ≤ N ≤ 100,000） 接下来 N 行，每行一个数，表示 Ai 。（1 ≤ Ai ≤ 100,000,000） 输出： 一个正整数，即每段和最大值最小为多少。 样例： 1234565 342451 16 1.思路 2.代码实现123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include<iostream>using namespace std;long long n, m, num[100005], rawl, rawr;long long func(long long x) { long long t = 0, now = 0; for (int i = 0; i < n; ++i) { if (now + num[i] > x) { t++; now = num[i]; } else if (now + num[i] == x) { t++; now = 0; } else { now += num[i]; } } if (now != ...

跳石头 原题链接：http://oj.haizeix.com/problem/394 一年一度的 “ 跳石头 ” 比赛又要开始了！ 这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。 为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 M 块岩石（不能移走起点和终点的岩石）。 输入： 第一行包含三个整数 L, N , M ，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 L ≥ 1 且 N ≥ M ≥ 0 。 接下来 N 行，每行一个整数，第 i 行的整数 Di （0 < Di < L），表示第 i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。 输出： 一个整数，即最短跳跃距离的最大值。 样例： 12345625 5 2 2111417 21 14 1.思路 2.代码实现12345678910111213141516171819202122232425262728293031323334353637383940414243#include<iostream>using namespace std;int ll, n, m, num[50005], rawl = 1000000000;int func(int x) { int cnt = 0, last = 0; for (int i = 1; i <= n + 1; ++i) { if (num[i] - last < x) { cnt++; } else { last = num[i]; } } return cnt;}int bs() { int l = rawl, r = ll; while (l != r) ...

原木切割 原木切割（整数二分） 二分答案（用答案进行切分）应用满足条件：①具有左右边界、②数据具有单调性 二分答案（答案需要是单调的）就是用函数替代数组，二分的本质是删掉不存在答案的区间 原题链接：http://oj.haizeix.com/problem/390 某林业局现在 N 根原木，长度分别为 Xi ，为了便于运输，需要将他们切割成长度相等的 M 根小段原木（只能切割成整数长度，可以有剩余），小段原木的长度越大越好，现求小段原木的最大长度。 例如，有 3 根原木长度分别为 6,15,22，现在需要切成 8 段，那么最大长度为 5。 输入： 第一行两个整数 N, M 。（1 ≤ N ≤ 100,000，1 ≤ M ≤ 100,000,000） 接下来 N 行，每行一个数，表示原木的长度 Xi 。（1≤ Xi ≤100,000,000） 输出： 输出小段原木的最大长度， 保证可以切出 M 段。 样例： 12343 861522 15 1.解题思路 根据每一个二分答案长度num[i]，利用fun()函数进行计算，求出其对应的能切出木头的段数 根据当前分出的段数s与题目给定需要切出的段数m进行比较，从而调整左右指针 当左右指针逼近到一定范围时，表示最佳答案已经找到、 判断二分的特殊类型为10类型 2.代码实现二分答案（整数二分）即用func()函数现求函数值，替代二分查找中在数组中进行二分操作 输入数据，并动态更新二分答案的右边界 套用二分的特殊10类型相关模型进行处理 根据临时长度mid与func()函数求出，原木能够切出的段数 比较mid切出的段数与给定需要切出的段数进行比较，以此调整左右指针 当左右指针逼近到一定范围，即找到最佳答案 输出bs()二分函数最后返回的结果 1234567891011121314151617181920212223242526272829303132333435363738#include<iostream>using namespace std;int n, m, num[100005], rawr;//求出当长度为mid时能切出的段数int func(int x) { int t = 0; for (int i = 0; i < n; ++i) { ...

暴躁的程序员 原题链接：http://oj.haizeix.com/problem/389 某公司的程序猿每天都很暴躁，因为他们每个人都认为其他程序猿和自己风格不同，无法一同工作。 当他们的工位的编号距离太近时，他们可能会发生语言甚至肢体冲突，为了尽量避免这种情况发生。现在公司打算重新安排工位，因为有些关系户的工位是固定的，现在只有一部分工位空了出来： 现在有 N 个程序猿需要分配在 M 个工位中，第 i 个工位的编号为 Xi，工位编号各不相同，现在要求距离最近的两个程序猿之间的距离最大，求这个最大距离是多少? Xi 和 Xj 工位之间距离为|Xi −Xj|。 输入： 输入共 M+1行，第一行两个整数 M, N（2 ≤ N ≤ M ≤ 100,000） 接下来 M 行，每行一个数表示剩余的工位的编号。 输出： 输出距离最近的两个程序猿之间的最大距离。 样例： 1234565 312849 13 1.解题思路 根据每一个二分答案长度num[i]，利用fun()函数进行计算，求出其对应的能够安排的程序员人数 根据当前能够分的人数s与题目给定需要分配的人数m进行比较，从而调整左右指针 当左右指针逼近到一定范围时，表示最佳答案已经找到 2.代码实现12345678910111213141516171819202122232425262728293031323334353637383940#include<iostream>#include<algorithm>using namespace std;int n, m, num[100005];int func(int x) { int t = 1, last = num[0]; for (int i = 1; i < n; ++i) { if (num[i] - last >= x) { ++t; last = num[i]; } } return t;}int bs() { int l = 1, r = num[n - 1] - num[0]; while (l != r) { ...

切绳子 切绳子（小数二分） 原题链接：http://oj.haizeix.com/problem/393 有 N 条绳子，它们的长度分别为 Li 。如果从它们中切割出 K 条长度相同的绳子，这 K 条绳子每条最长能有多长？ 答案保留到小数点后 2 位（直接舍掉 2 位后的小数）。 输入： 第一行两个整数 N 和 K，接下来 N 行，描述了每条绳子的长度 Li 。 输出： 切割后每条绳子的最大长度，保证答案大于零。 样例： 123454 118.027.434.575.39 12.00 1.思路①整数二分与小数二分的不同点、②保留两位小数直接舍去的两种方法 2.代码实现12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include<iostream>#include<cmath>#include<cstdio>using namespace std;int n, m;double num[10005], mmax;int func(double x) { int cnt = 0; for (int i = 0; i < n; ++i) { cnt += num[i] / x; } return cnt;}double bs() { double l = 0, r = mmax; //当差值大于预设精度则一直求解 while(fabs(l - r) > 0.00005) { double mid = (l + r) / 2; //根据mid值确定能够切出的绳子数量 int s = func(mid); if (s >= m) { l = mid; } else { r = mid; } } return r;}int main() { cin >> n ...