臭鱼烂虾学代码-二分法初学
2021/10/18 23:39:59
本文主要是介绍臭鱼烂虾学代码-二分法初学,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
根据百度百科信息,二分法的算法:二分法查找适用于数据量较大时,但是数据需要先排好顺序。或者说,有一个临界值,临界值之前满足条件,超过临界值之后不满足条件。
一般来说,二分法的时间复杂度为O(logN),比一般遍历O(N)要优秀。日常生活中,在一串(有序的)数据中,要找到一个特定对象,也可以使用二分法来查找来使操作难度降低,最简单的例子就是翻字典。
我二分法的引入是砍树问题(洛谷p1873)
n棵树高度分别为a1,a2,...,an,对于一个砍树高度h,可以锯下并收集到每棵树比h高的部分的木料,现在需要求高度h使得能够收集到长度为m的木材。其中n<=10e6,树高不超过10e9。例如,有5棵树,需要收集到20单位的木材,每棵树的高度分别是【4,42,40,26,46】,需要将锯子的高度调整为36,这样可以分别锯下【6,4,10】高度的木材。如果锯子高度再高一点就不能满足要求了。
二分模板如下:
bool check(long long x) { //判断条件; } long long l=0,r=1e18,ans; while(l<=r) { long long mid=(l+r)>>1;//X>>1=X/2 if(check(mid)){ ans=mid; r=mid-1; } else l=mid+1; }
最简单的二分如下(相当于lower_bound,upper_bound需要加#include<bits/stdc++.h>头文件 using namespace std命名空间清零):
#include<stdio.h> int low = 0; int high = 100000; int mid = 0; int n; bool check(int mid){ return mid>n; } int main(){ scanf("%d",&n); while(low<=high){ mid = (low + high)/2; if(mid == n){ printf("%d",mid); } if(check(mid)){ high = mid - 1; } else if(!check(mid)){ low = mid + 1; } } return 0; }
这篇关于臭鱼烂虾学代码-二分法初学的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求