二分法（分巧克力、跳石头、一元三次方程求解）
1.分巧克力
题目描述
儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 N 块巧克力，其中第 i 块是 Hi×Wi 的方格组成的长方形。为了公平起见，
小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足：
形状是正方形，边长是整数;
大小相同;
例如一块 6×5 的巧克力可以切出 6 块2×2 的巧克力或者 2 块 3×3 的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？
输入描述
第一行包含两个整数 N,K (1≤N,K≤10^5)。
以下 N 行每行包含两个整数 Hi,Wi (1≤Hi,Wi≤10^5)。
输入保证每位小朋友至少能获得一块 1×1 的巧克力。
输出描述
输出切出的正方形巧克力最大可能的边长。
样例输入
2 106 55 6样例输出2
1.二分法：如果这个数check为True,就往后取，如果为False，就往前去
一直到左右相等
2.不同于找数，这个是找最大数
n, k = map(int, input().split())def check(d): global w, h res = 0 for i in range(len(w)): res += (w[i]//d) * (h[i]//d) if res >= k: return Truew = []h = []for i in range(n): a, b = map(int, input().split()) w.append(a) h.append(b)L, R = 1, 100000while L < R: mid = (L+R)//2 if check(mid): L = mid+1 else: R = midif check(L):#最后一步是R=mid,但是左边的left没check print(L)else: print(L-1)
2.跳石头
题目描述
一年一度的「跳石头」比赛又要开始了！
这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。
为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走M块岩石（不能移走起点和终点的岩石）。
输入描述
输入文件第一行包含三个整数 L，N，M分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。
接下来 N行，每行一个整数，第 ii行的整数 Di（0<Di<L）表示第 ii 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。
其中，0≤M≤N≤5×10^4，1≤L≤10^9。
输出描述
输出只包含一个整数，即最短跳跃距离的最大值。
样例输入
25 5 2211141721样例输出
4
1.在 n块岩石中选 m块石头，有 m!/(n−m)!n! 种组合，实在是太多了。转换思路，现在我们不去找搬走石头的各种组合，而是给出一个距离 d，检查能不能搬走 m 块石头而得到最短距离 d。
(判断它与前一块石头的距离是不是小于最短距离，如果小于最短距离，这块石头就得移走。）
2.如果总共搬的石头小于给的数目，说明距离d可以达到。
3.用二分查找，同巧克力，找到符合条件的最大数。
l,n,m=map(int,input().split())p=[]for i in range(n): p.append(int(input()))def check(d): pos=0 num=0 for i in range(n): #两个石块之间的距离大于d(最小的距离可能是d),要搬走的石块数 if (p[i]-pos)<d: num+=1 else: pos=p[i] if num<=m: return True else: return FalseL,R=1,lwhile L<R: mid=(L+R)//2 if check(mid): L=mid+1 else: R=midif check(L): print(L)else: print(L-1)
n = input().split()a,b,c,d = eval(n[0]),eval(n[1]),eval(n[2]),eval(n[3])def y(x): return a*x*x*x+b*x*x+c*x+dfor i in range(-100,100): left=i right=i+1 y1=y(left) y2=y(right) if y1==0: print("{:.2f}".format(left),end=" ") if y1*y2= 0.001: #eps=0.001 mid = (left+right)/2 if y(mid)*y(right) <=0: left = mid else: right = mid print("{:.2f}".format(right),end=" ")
.