高端网站设计公司排行榜,成品网站管系统,百年人寿保险公司官网,wordpress除了首页全是404写在前面 二分是一种常用且非常精妙的算法#xff0c;常常是我们解决问题的突破口。二分的基本用途是在单调序列或单调函数中做查找。因此当问题的答案具有单调性时#xff0c;就可以通过二分把求解转化为判定。进一步地#xff0c;我们还可以通过三分法解决单调函数的极值以… 写在前面 二分是一种常用且非常精妙的算法常常是我们解决问题的突破口。二分的基本用途是在单调序列或单调函数中做查找。因此当问题的答案具有单调性时就可以通过二分把求解转化为判定。进一步地我们还可以通过三分法解决单调函数的极值以及相关问题。 刷题进度 二分答案2/4 二分查找 问题解决进度 Q1 一、二分 二分法在一个单调有序的集合或函数中查找一个解每次分为左右两部分判断在哪个部分中并调整上下界直到找到目标元素每次二分后都将舍弃一半的查找空间因此效率很高。 显然二分算法的复杂度为O(二分次数×单次判定复杂度) ……可怜的我依旧不会算复杂度QAQ…… 二、二分核心代码 1.整数定义域 int work(int l,int r){int l-INF,rINF;//根据题目要求改变左右端点的初始值while(lr){int mid(lr)1;if(check(mid1)) lmid1;//如果符合要求就继续二分查找else rmid;}return l;
} 2.实数定义域 double work(double l,double r){//根据题目要求确定精度dltdouble mid;while(fabs(l-r)dlt){//实数比较大小此句相当于lr
//补充:fabs(x1)很abs(x2)都表示求绝对值只不过x1是实数x2是整数mid(lr)/2.0;if(check(mid)) rmid;else lmid;}return l;
} TIP如果指定二分的次数为t那么对于初始的求解区间长度L算法结束后r-l的值为L/2t 三、二分法常见模型 1.二分答案 最小值最大或最大值最小问题这类双最值问题常常选用二分法求解也就是确定答案后配合贪心、DP等其他算法检验这个答案是否合理将最优化问题转换为判定性问题。 【例 1】 将长度为n的序列分成最多m个连续段求所有分法中每段和的最大值的最小是多少 一些题目 LuoguP1024 LuoguP2678 LuoguP3957 Luogu二分答案 2.二分查找 用具有单调性的布尔表达式求解分界点。 【例 2】 在有序数列中求数字x的排名。 一些题目 Luogu二分查找 3.代替三分 有时对于一些单峰函数我们可以用二分导函数的方法求解函数极值这时通常将函数的定义域定义为整数域求解比较方便。 四、典型例题 【例 1】愤怒的牛(Bzoj 1734) 1.题目大意 已知有n间牛舍和每间牛舍的位置现在要求一种方案使得m头牛两两之间的最小距离尽可能大求这个最大的最小距离。 2.思路 这是一道最大值最小化的典型题目。 设C(d)表示可以安排牛的位置并使得最近的两头牛距离≥d 那么问题就转化为了求满足C(d)的最大的d最近的间距≥d可以看成是所有间距都≥d因此满足C(d)的条件就是任意两头牛的位置≥d 于是可以贪心求解 1对牛舍的位置x进行排序 2把第一头牛放入x0的牛舍 3如果第i头牛放入了xj的牛舍则第i1头牛就要放入满足xjd≤xk的xk最小的牛舍中 对x的排序只要在开始时进行一次就可以了每一次判断对每头牛最多进行一次处理因此算法的时间复杂度为O(nlogn) 3.代码 咕咕咕咕咕 【例 2】Best Cow Fences(Poj 2018) 1.题目大意 给定一个长度为n的正整数序列A求一个平均数最大的长度≥L的子序列。 2.思路 二分答案mid合法的条件为“存在一个长度≥L的子序列平均数≥mid” 如果把数列中的每个数都减去二分的值合法的条件就转化为“存在一个长度≥L的子序列子序列每一项相加的和≥0” 接下来就是着重解决两个问题 1求一个子序列要求和最大没有“长度≥L”的限制 无长度限制的最大子序列和问题是一个经典问题只需O(n)扫描该数列不断地把新的数加入子序列当子序列的和变成负数时把当前的整个子序列清空。扫描过程中出现的最大子序列和即为所求。 2求一个子序列要求和最大且子序列的长度≥L 子序列和可以转化为前缀和相减的形式即设sumi表示A1Ai的和则有 maxi-j≥L{Aj1Aj2……Ai}maxL≤i≤n{sumi-min0≤j≤i-L{sumj}} 这个式子啥意思呀QAQ 这个式子随着i的增长j的取值范围0i-L每次只会增加1。也就是说每次只会有一个新的值进入min{sumj}的候选集合所以没有必要每次循环枚举j次只需要用一个变量记录当前最小值每次与新的取值sumi-L取min就可以了。 解决了这两个问题后我们只需要判断最大子序列和是不是非负数就可以确定二分上下界的变化范围了。 3.代码 咕咕咕咕咕转载于:https://www.cnblogs.com/THWZF/p/10365241.html
