二分法

原题链接 洛谷题解很详细，自己写了些理解在代码注释里 代码 #include<bits/stdc++.h> using namespace std; int atch[50005]={0}; int vis[50005]={0}; vector<int> G[505]; int weiy(int n ......

题目描述在这里：P1678 这道题用二分的思路就很容易想出，先把学校分数排好序，根据不满意度的定义，我们只需要每次找到第一个大于学生成绩的学校分数，然后再和最后一个小于学生分数的院校分数分别与学生成绩做差再打绝对值进行比较，取最小的一个累加到ans里就好啦 代码如下 #include<iostrea ......

题目描述见此：P1024 如何求一个方程的根呢qwq 首先，根是什么，函数y＝f(x)有零点 ⇔ 方程f(x)＝0有实数根 ⇔ 函数y＝f(x)的图象与x轴有交点。回顾我们高一学过的一个定理： 零点存在性定理： 如果函数y＝f(x)在区间[a, b]上的图象是连续不断的一条曲线，并且有f(a)·f( ......

题目描述见：P1873 思路比较明确qwq因为答案显然满足单调性：当x超过某个数一定是错的（收集的木材大于m)，而小于x一定是对的，并且x是从0一直递增。故我们只需二分法找到x。 直接看代码吧qwq精髓是check函数直接模拟题目要求ww #include <iostream> using name ......

题目描述见：P1102 qwq大致思路是将A-B=C变成A=B+C，其中C是确定的，并且题目说重复的也算ww（如果需要不重复的话开两个数组，给其中一个数组去重就行了qwq)那么在数组有序的情况下只需要枚举数组中的每一个数，然后用二分来找存在几个B+C，因为数组有序所以B+C一定是连续的，故寻找第一个 ......

题目描述 思路 基础二分查找模板的考察。 方法一： class Solution { public int search(int[] nums, int target) { if (nums == null || nums.length == 0) return -1; int left = 0, ......

二分查找 局部最小问题 问题描述： 对于一个数组，相邻值不等。查找出该数组中满足局部最小的值。 局部最小： x[0]<x[1] 2 x[n-1]<x[n-2] x[i-1]>x[i] && x[i+1]>x[i] 算法思路： 首先检测首尾是否满足局部最小，若满足则查找成功，退出算法； 若均不满足，则 ......

1. 简介故事分享🏬： 有一天小明到图书馆借了 N 本书，出图书馆的时候，警报响了，于是保安把小明拦下，要检查一下哪本书没有登记出借。小明正准备把每一本书在报警器下过一下，以找出引发警报的书，但是保安露出不屑的眼神：你连二分查找都不会吗？于是保安把书分成两堆，让第一堆过一下报警器，报警器响；于是再 ......

二分图最大匹配和二分图最大权完美匹配 二分图最大匹配 题目描述 对于一个二分图，求其最大匹配的边数（任意一个点只能匹配另一个点） 算法解析 使用匈牙利算法。遍历每一个左部点，若发现它所连到的右部点中有未被匹配的点就选择连接；若右部点已被匹配，就询问匹配该右部点的点能否更换至另一个点，递归执行直到发现 ......

题目 搜索旋转排序数组 整数数组 nums 按升序排列，数组中的值 互不相同 。 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], n ......

题目链接：https://www.luogu.com.cn/problem/P1824 题目大意： 本题相当于在 \(n\) 个数中选 \(c\) 个数，使得这 \(c\) 个数中相差最小的两个数之差尽可能地大。 解题思路： 我们首先可以给 \(a_1 \sim a_n\) 从小到大排一下序（这里有 ......

【1】保护大地球 题目链接 地球是一个坐标平面，您的任务是保护它。 google earth 给定 K (地球上的人数），你必须制作一个保护罩来保护他们。 求以坐标 (0, 0) 为圆心的圆，且能容纳 K 个人的最小的圆的半径。已知一个人只能站在整数坐标上，且 两个人不能站在同一位置。 注 1：一个 ......

目录什么是二分查找算法原理示例代码（python） 什么是二分查找 二分查找也叫折半查找，是在有序数组查找特定元素的算法。算法的时间复杂度为O(logn)。 算法原理 定义一个有序数组， 初始化left数组第一个元素序号，right为数组最后一个元素序号，middle为left和right中间元素序 ......

LeetCode 704 二分查找 题目链接 704.二分查找 二分法 确定区间 （循环不变量）：对于有序数组，定义循环区间二分查找元素 LeetCode 27.移除元素 题目链接：27.移除元素 快慢指针，快指针查，慢指针存 ......

一、数组理论基础 学习前： 1. 数组定义 一些在内存上连续存储的相同数据类型的数据的集合 2. 数组特征 便于查询数组元素，不便于增删数据元素 学习后： 对于Java，二维数组不一定在内存上连续。如int[i][j],唯一确定的是int[i][]在内存上连续 二、704. 二分查找 LeetCod ......

Leetcode704：二分查找 今日学习的文章链接： 代码随想录 (programmercarl.com) 题目链接： 704. 二分查找 - 力扣（LeetCode） ● 自己看到题目的第一想法 这题我会，但是还没明白卡尔说的循环不变量是什么意思。 我的固定思路就是，target比中间值大，左指 ......

Day1二分查找，移除元素 By HQWQF 2023/12/13 笔记 704. 二分查找 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。 解法：使用二分查找来在一个有序的数 ......

LeetCode704.二分查找 二分查找是一种基础的算法，其核心思想在高中数学中就已经被大家所熟知了，然而对于代码的实现，其细节问题常常令人头疼，比如while循环的条件是什么？middle是该+1还是-1？这些问题需要有一个清晰的认知。 题目链接如下:704.二分查找 Carl的讲解链接：二分查 ......

今日一道编程题 第八届蓝桥杯赛题中的分巧克力问题（用二分法实现） 问题描述如下： 儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。小明一共有N块巧克力，其中第i块是Hi x Wi的方格组成的长方形。为了公平起见，小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧 ......

易错 在清除当前区间处理时的影响时，通常有两种做法：（下以区间第 \(k\) 小为例 若个数 res < 待查询第 k 小时，一般就有两种处理方法： k -= res，最后递归的时候直接清空 bit。 k 不变，先递归右区间，清空 bit，再递归左区间。 正确性 在没有中途修改，或者可以认为所有的修 ......

题目 在排序数组中查找元素的第一个和最后一个位置 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target，返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此 ......

定义 节点由两个集合组成 两个集合内部没有边的图 换言之，存在一种方案，将节点划分成满足以上性质的两个集合 性质 如果两个集合中的点分别染成黑色和白色，可以发现二分图中的每一条边都一定是连接一个黑色点和一个白色点 二分图不存在长度为奇数的环 为什么？因为每一条边都是从一个集合走到另一个集合，只有走偶 ......

时间复杂度为Θ(n^3) const int inf =0x3f3f3f3f; const int N=505; long long w[N][N]; long long la[N],lb[N]; bool va[N],vb[N]; long long match[N]; long long n,m ......

二分图最大匹配可以转换成网络流模型。 将源点连上左边所有点，右边所有点连上汇点，容量皆为1。原来的每条边从左往右连边，容量也皆为1，最大流即最大匹配。 如果使用 Dinic 算法 求该网络的最大流，可在O(sqrt(n) * m)求出。 #define N 1010 #define M 200001 ......

染色法判别二分图 —— 模板题 AcWing 860. 染色法判定二分图 时间复杂度是 \(O(n+m)\), \(n\) 表示点数，\(m\) 表示边数 int n; // n表示点数 int h[N], e[M], ne[M], idx; // 邻接表存储图 int color[N]; // 表 ......

金牌导航-二分图匹配 例题A题解 将行和列相匹配，跑最小割即可。 例题A代码 #include<bits/stdc++.h> using namespace std; inline int read(){ int x = 0, f = 1;char ch = getchar(); while(ch ......

个人笔记，欢迎补充、指正。 此次完全以个人理解来写。 整数二分 整数二分有两种，分别是找左边界和找右边界。 寻找符合要求的左边界：绿色点 int bsearch_1(int l, int r) { while (l < r) { int mid = l + r >> 1;//对应下界，最左 if ( ......

定义 有点扩展域并查集的意思~ 如果一张无向图的 \(N\) 个节点 \((n\geq 2)\) 可以分成 \(A,B\) 两个非空集合，其中 \(A\cap B = \emptyset\)，并且在同一集合内的点之间都没有边相连，那么称这张无向图为一张二分图。\(A\)、\(B\) 分别称为二分图的 ......

2023.12.6 cf1902B 二分 一般来讲我们会在以下情况用到二分： 求单调函数的零点 求最小值的最大，或最大值的最小 很难直接算出答案，但是很好判定答案合不合法 二分答案和二分查找差不多，就是check函数内是贪心dp之类的东西 本题思路 观察题目数据，算法复杂度在logn及以下为宜，考虑 ......

有些时候，我们二分答案以后，就会去找例如 “小于 \(mid\) 的值个数” 这样的值，要用线段树、trie 等数据结构。 然而线段树节点本身支持二分，直接在结构上二分是 \(\Theta(\log n)\) 的，但是外面二分答案再笨拙地查询是 \(\Theta(\log ^2 n)\) 的。 你都 ......