Doran_dinosaur

二分答案

BFS(10) DFS(4) 前缀和(2) 排序算法(1) 树状数组(1) 模拟(1) 线性DP(8) 线段树(3) 背包DP(3) 蓝桥杯(4) 题解(13)

/ 注册

全部文章 / 二分答案（共10篇）

P1873 砍树

P1873 砍树题目分析：答案区间[l,r] (l = min(a[i]),r = max(a[i])) 找最优解：最高砍树高度 mid取(l + r + 1) >> 1,偏右注意：二分出现死循环往往是mid写错了代码如下: #include<cstdio>...

2021-01-04

0 670

P1843 奶牛晒衣服

P1843 奶牛晒衣服题目分析：数据范围：为了避免踩坑，用long long型求解弄干所有衣服的时间二分答案区间[l,r] (l = 1,r = inf) 注意：踩坑了，int改半天，w[i] - a * x里面乘以x可能爆int，用long long啊代码如下： #in...

2021-01-04

0 723

P1661 扩散

P1661 扩散题目分析：求解最早的时刻所有点形成连通块连通块需要用到并查集，时间从小到大符合单调用二分答案区间[l,r] (l = 1,r = inf) 代码如下： #include<cstdio> #include<cmath> #include<cst...

2021-01-04

0 586

P1577 切绳子

P1577 切绳子题目分析：有n条绳子，分为相同的k条，求每条最长浮点数二分法：一条绳子最多分(a[i] / x)条,答案区间[l,r] (db l = 0,r = inf) 代码如下: #include<cstdio> #include<cmath> #inclu...

2021-01-04

0 657

P1570 KC喝咖啡

P1570 KC喝咖啡题目分析：一个裸的01分数问题答案区间[l,r] (l = 0,r = inf) 代码如下： #include<cstdio> #include<cmath> #include<cstring> #include<iostr...

2021-01-04

0 567

P1396 营救

P1396 营救题目分析: 并查集+二分法答案区间[l,r] (l 为边的最小值，r 为边的最大值) 代码如下: #include<cstdio> #include<cmath> #include<cstring> #include<iostre...

2021-01-04

0 647

P1281 书的复制

P1281 书的复制题目分析：求解复制时间（抄写页数最多的人用去的时间）最短转换为：长度为m的数列分为k段，每段和的最大值，如何分才能使得最大值最小注意：如果有多解，则尽可能让前面的人少抄写前面的人少抄写，就尽可能的用后面的人，那么从后往前遍历，最后反转一下输出答案代码如下: ...

2021-01-04

0 523

P1182 数列分段 Section II

P1182 数列分段 Section II 题目分析：数据大小把长度为N的数列分为M段，找出每段和的最大值中的最小值二分法：找出答案区间每段和最大值[l,r] 答案存在一个分界点，[l,x] 为非可取解，x为最优解,[x + 1,r]为可取解区间左端点为数列的最大值，右端点为数列的和整数...

2021-01-03

0 659

一元三次方程求解

一元三次方程求解题目分析：根的范围在-100到100之间根与根之间差的绝对值>=1，我们可以用二分判断答案所在最小区间1，求解答案区间在[i,i + 1] (-100<=i<100) 实数范围用浮点数二分代码如下： #include<cstdio> #inc...

2021-01-03

0 546

小咪买东西（0/1分数规划）

小咪买东西题目分析： 1.总价值/总花费=max，设总价值为b,总花费为a,答案为未知：b/a = x2. 对x进行二分处理（取值范围（0，inf））3. 取k个物品，那么进行排序取（bi/ai)前k个最大的代码如下： #include<bits/stdc++.h> using n...

2020-11-20

2 616