在计算机学习过程中，算法也是大头，相当重要。 无论是学术界还是工业界，拥有极强的编码能力都非常受欢迎，作为未来的程序员，算法不能掉以轻心。 为此，专门开设本专栏，促进算法的学习、算法的问题、大脑的活动、总结。
标题来源： ZYJ老师OJ标题(下一周) ) ) ) ) ) ) ) ) ) )标题) ) ) ) ) ) )标题) ) ) ) ) ) )标题) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) 652 ) ) ) )
文章目录一、基本二分法描述二、主题实战一、木棒分割(入门)二、石头移动)困难)三、快递包裹一、基本二分法描述二分搜索(英文： binary search )，又称折半搜索、对数搜索，在有序排列中寻找特定元素查找过程从数组的中间元素开始，如果中间元素是要查找的元素，则查找过程结束。 如果特定元素大于或小于中间元素，则按数组大于或小于中间元素的一半进行搜索，然后与第一个元素进行比较。 如果步骤数组为空，则意味着找不到。 该搜索算法在每次比较时将搜索范围缩小一半。 复杂度分析：最坏情况下关键词比较次数为log2(n1 )，且期望时间复杂度为o ) O(log2n )；
思考：一直不太清楚，这里可以定为l=0，h=10吗？ (好像不太擅长)，所以，设置11，原理是什么呢？ 一个trick :在主题中，可以首先判断这是int类型的二分问题还是双精度类型。 二、主题实战1 .棒的分割(入门) ) ) ) ) ) ) ) ) ) ) ) )。
我们有n根的木棍。现在从这些木棍中切割出来m条长度相同的木棍，问这m根木棍最长有多长？
输入数据
在第一行输入两个数字。 n(1=n=1000 )是木棒的数量，m ) m(1=m=1000 )是相同长度的木棒数量之后的n个正整数，表示原始木棒的长度(=10000 )
输出数据
每组输出一行结果，表示切断后绳子的最长长度。 留下两位小数
样品输入
4 5
5 6 7 8
样品输出
4.00
分析：求最长长度，二分法容易想到。 分支的是木棍的长度，如果初始化的l=0，h=max (木棍的长度(check ) mid )通过，长度在mid以下的部分就去除，同时用单独的ans记录现在的结果) ps:设置ans用自己的小TTS
代码：
# include cstdio # include cmath # includecstdlib # includeiostreamintn，m； int a[10000]； using namespace std； 调查布尔检查(doublex ) { //check函数是否成立。 传递的参数为双精度int cnt=0； for(intI=0； i n； I ) {cnt =a[i]/x； (if ) CNT=m ) {return true； }return false； (}int main ) ) {cin n m； int lmax=0； double ans=1； for(intI=0； i n； I () {cin a[i]； lmax=max(a[I]，lmax )； }double l=0，h=lmax 1； //避免此处存在无法获取双精度mid的边界值； while(h-L0.0001 ) ) /浮点数比较大小惯用法mid=(LH )/2； if(check(mid ) ) {ans=mid； l=mid； //这里需要记住！ 更新上下边界时直接变更为mid； (else ) h=mid； }printf('%.2lf”，ans )； //浮点数只要输出指定位数并设为printf即可}代码中已经详细说明了解释，但这个问题也是二分法更入门，所以省略说明。
2 .石头移动(困难)主题说明
有一条河，河中央有几块石头，知道石头的数量和相邻两块石头之间的距离。 可以去掉一些石头。 最多清除m块石头后，不能顺利清除两块石头。 相邻两块石头之间的距离最小值是多少？
输入数据
在第一行输入两个数字。 n(2=n=1000 )是石头的个数，m ) m(0=m=n-2 )是可拆除石头数之后的n-1个数字，表示顺序和相邻两块石头之间的距离d(d=1000 )
输出数据
输出最小距离的最大值
样品输入
4 1
1 2 3
样品输出
3
分析：首先依据题目中“距离最小值最大”的无脑选择二分法。 相邻两块石头之间的距离最小值是被二分对象，l=0，h=max (未处理前的间隔)。 而且，只能通过移动比m小的棋子能否实现check ) mid ) )因为如果不限定m，无论如何也只能实现，例如将除了两端以外的东西全部取下)。 当然，思路很难思考，check函数也不容易实现。
代码：
# includeiostreamusingnamespacestd； int n，m； int a[1000]； 输入
t dis[1000];bool check(int x) {cout << "coming";int cnt = 0;//记录移除石头的个数//检查：让任意相邻两石头的距离>=x,然后判断移除的石头个数是否<=mint i = 0;for (int j = 1; j < n; j++) {if (dis[j] - dis[i] < x) {cnt++;}else {i++;j++;}}if (cnt > m) return false;return true;}int main() {cin >> n >> m;for (int i = 0; i < n-1 ; i++) { //一共n-1个间距cin >> a[i]; //a[i]表示第i个间距dis[i+1] = dis[i] + a[i];//dis[i]表示0~i(标号，从0开始)的距离}dis[n] = dis[n - 1];//不可或缺int l = 0, h=dis[n], mid;int ans=0;while (l < h) {mid = (l + h) / 2;if (check(mid)) {l = mid+1;ans = mid;}else {h = mid-1 ; //此处需要处理！我也不知该如何判断。。。}}cout << ans;}有一个疑惑，关于h，很多人都是以一个极大数比如1000000作为初始化，我不理解？
3.快递包裹题目描述
一个快递公司要将n个包裹分别送到n个地方，并分配给邮递员细心的茉莉一个事先设定好的路线，细心的茉莉需要开车按照路线给的地点顺序相继送达，且不能遗漏一个地点。细心的茉莉得到每个地方可以签收的时间段，并且也知道路线中一个地方到下一个地方的距离。若到达某一个地方的时间早于可以签收的时间段，则必须在这个地方停留至可以签收，但不能晚于签收的时间段，可以认为签收的过程是瞬间完成的。
为了节省燃料，细心的茉莉希望在全部送达的情况下，车的最大速度越小越好，就找到了你给他设计一种方案，并求出车的最大速度最小是多少。
输入数据
第 1 行为一个正整数 n (n<2×104)， 表示需要运送包裹的地点数。
下面 n 行，第 i+1 行有 3 个正整数 xi,yi,si， 表示按路线顺序给出第 i 个地点签收包裹的时间段为 [xi,yi]， 即最早为距出发时刻 xi， 最晚为距出发时刻 yi， 从前一个地点到达第 i 个地点距离为 si， 且保证路线中 xi 递增。
可以认为 s1 为出发的地方到第 1 个地点的距离，且出发时刻为 0 。
输出数据
仅包括一个整数，为车的最大速度最小值，结果保留两位小数。
样例输入
3
1 2 2
6 6 2
7 8 4
样例输出
2.00
样例说明
第一段用1的速度在时间2到达第1个地点，第二段用0.5的速度在时间6到达第2个地点，第三段用2的速度在时间8到达第3个地点。