前言
简介：涉及二分，题目源于洛谷
建议大家先自行尝试解题，同时阿鑫的水平不高，所以题解也通常并不算好，建议大家可以在洛谷相关题目的题解处查看其他大佬的题解，阿鑫的题解简单看看就好。
练习
洛谷P1024 [NOIP2001 提高组] 一元三次方程求解
题目链接：洛谷P1024 [NOIP2001 提高组] 一元三次方程求解
题目描述
有形如：a x3 + b x2 + c x + d = 0 这样的一个一元三次方程。给出该方程中各项的系数（a,b,c,d均为实数），并约定该方程存在三个不同实根（根的范围在 -100 至 100 之间），且根与根之差的绝对值 ≥1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后 2 位。
提示：记方程 f(x) = 0，若存在 2 个数 x1和 x2，且 x1 < x2 ，f(x1) * f(x2) < 0，则在 (x1, x2) 之间一定有一个根。
输入格式
一行，4 个实数 a, b, c, d。
输出格式
一行，3 个实根，从小到大输出，并精确到小数点后 2 位。
输入输出样例
输入
1 -5 -4 20
输出
-2.00 2.00 5.00
说明/提示
【题目来源】
NOIP 2001 提高组第一题
解题思路：
依据题意，若存在 2 个数 x1和 x2，且 x1 < x2 ，f(x1) * f(x2) < 0，则在 (x1, x2) 之间一定有一个根。
根的范围在 -100 至 100 之间,所以我们对这区间内进行二分深搜。
ac题解
//时间：16ms(15ms) 内存：808.00KB
#include <bits/stdc++.h>
using namespace std;
float a,b,c,d,x[4];
int flag=0;
void dfs(float l,float r){
float lx,rx;
lx=(a*l*l*l)+(b*l*l)+(c*l)+d; //左值
rx=(a*r*r*r)+(b*r*r)+(c*r)+d; //右值
if(lx*rx<0){ //左值右值相乘为负，其中一定有根
if(r-l<=0.01){ //精确到小数点后 2 位（0.01）
for(int i=1;i<=flag;i++){
if(abs((l+r)/2-x[flag])<1) return; //防止取到重复解
}
flag++;
x[flag]=(l+r)/2; //记录答案
}
}
if(r-l<0.01||flag>=3){
return; //如果精确到小数点后2位还没有答案或者答案有了3个，结束搜索。
}
dfs(l,(l+r)/2);//搜索左边
dfs((l+r)/2,r);//搜索右边
}
int main()
{
cin>>a>>b>>c>>d;
dfs(-100,100);
printf("%.2f %.2f %.2f\n",x[1],x[2],x[3]);
return 0;
}
洛谷P2678 [NOIP2015 提高组] 跳石头
题目链接：洛谷P2678 [NOIP2015 提高组] 跳石头
题目背景
一年一度的“跳石头”比赛又要开始了!
题目描述
这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。
为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 M 块岩石（不能移走起点和终点的岩石）。
输入格式
第一行包含三个整数 L,N,M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 L≥1 且 N≥M≥0。
接下来 N 行，每行一个整数，第 i 行的整数 Di( 0 < Di < L)， 表示第 i块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。
输出格式
一个整数，即最短跳跃距离的最大值。
输入输出样例
输入
25 5 2
2
11
14
17
21
输出
4
说明/提示
输入输出样例 1 说明：将与起点距离为 2和 14 的两个岩石移走后,最短的跳跃距离为 4(从与起点距离 17 的岩石跳到距离 21 的岩石,或者从距离 21 的岩石跳到终点)。
另：对于 20%的数据,0 ≤ M ≤ N ≤ 10。
对于50%的数据,0 ≤ M ≤ N ≤ 100。
对于 100%的数据,0 ≤ M ≤ N ≤ 50,000,1 ≤ L ≤ 1,000,000,000。
解题思路：
ac题解