🐏小羊简介：
💖博客主页：小羊不会飞
🚀年龄：20 大二在读
💪爱好：干饭，运动，码代码，看书，旅游
📃即将更新：
🎯算法修炼23招----第二招
🚍：感兴趣的朋友，赶紧上车吧！！
🎉欢迎关注🔍点赞👍收藏🎇留言📙
🎄有任何疑问，欢迎留言讨论！！！
😶🌫️二分
✨例1：木材加工
✨例2：砍树
🚀写在最后
✨例1：木材加工
P2440 木材加工
题目背景
要保护环境
题目描述
木材厂有 n根原木，现在想把这些木头切割成 k 段长度均为 l的小段木头（木头有可能有剩余）。
当然，我们希望得到的小段木头越长越好，请求出 l的最大值。
木头长度的单位是 cm，原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。
例如有两根原木长度分别为 11 和 21，要求切割成等长的 6 段，很明显能切割出来的小段木头长度最长为 5。
输入格式
第一行是两个正整数 n,k分别表示原木的数量，需要得到的小段的数量。
接下来 n行，每行一个正整数 Li，表示一根原木的长度。
输出格式
仅一行，即 l的最大值。
如果连1cm 长的小段都切不出来，输出
0。输入输出样例
输入 #1
3 7 232 124 456输出 #1
114说明/提示
数据规模与约定
对于 100% 的数据，有 1≤n≤10^5 , 1≤k≤10^8，1≤Li≤10^8(i∈[1,n])
package 高校算法社区每日一题;
import java.util.Scanner;
/**
* @author yx
* @date 2022-04-27 11:28
*/
public class 洛谷P2440木材加工__二分 {
static int tree[]=new int[100008];
static int n;
static int m;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n=scanner.nextInt();
m=scanner.nextInt();
int left=0;
int right=0;
for (int i = 1; i <=n ; i++) {
tree[i]=scanner.nextInt();
right=Math.max(right,tree[i]);
}
while (left<right){
int mid=(left+right+1)>>1;
if(check(mid)>=m){
left=mid;
}else {
right=mid-1;
}
}
System.out.println(left);
}
static long check(int mid){
long sum=0;
for (int i = 1; i <=n ; i++) {
if(tree[i]>mid){
sum+=tree[i]/mid;
}
}
return sum;
}
}
💐题解分析：
1、定义左指针left，右指针right（取输入数据的最大值），mid中间值
2、
int mid=(left+right+1)>>1;每次对mid除2并进行向上取整
3、
if(check(mid)>=m){ left=mid; }else { right=mid-1; }不断缩小区间的范围
4、
static long check(int mid){ long sum=0; for (int i = 1; i <=n ; i++) { if(tree[i]>mid){ sum+=tree[i]/mid; } }对段数进行求和，返回求和的值
💐难点分析：
1、
int mid=(left+right+1)>>1;向上取整，并且防止程序陷入死循环，这个大家可以把“+1”去掉然后自己模拟推导一遍即可
2、二分必备check()函数，结合语句起到一个方向针的作用
3、对于边界问题的考虑
✨例2：砍树
P1873 [COCI 2011/2012 #5] EKO / 砍树
题目描述
伐木工人 Mirko 需要砍 M 米长的木材。对 Mirko 来说这是很简单的工作，因为他有一个漂亮的新伐木机，可以如野火一般砍伐森林。不过，Mirko 只被允许砍伐一排树。
Mirko 的伐木机工作流程如下：Mirko 设置一个高度参数 H（米），伐木机升起一个巨大的锯片到高度 H，并锯掉所有树比 H 高的部分（当然，树木不高于 H 米的部分保持不变）。Mirko 就得到树木被锯下的部分。例如，如果一排树的高度分别为 20,15,10 和 17，Mirko 把锯片升到 15 米的高度，切割后树木剩下的高度将是 15,15,10 和 15，而 Mirko 将从第 1 棵树得到 5 米，从第 4 棵树得到 2 米，共得到 7 米木材。
Mirko 非常关注生态保护，所以他不会砍掉过多的木材。这也是他尽可能高地设定伐木机锯片的原因。请帮助 Mirko 找到伐木机锯片的最大的整数高度 H，使得他能得到的木材至少为 M 米。换句话说，如果再升高 1 米，他将得不到 M 米木材。
输入格式
第 1 行 2 个整数 N 和 M，N 表示树木的数量，M 表示需要的木材总长度。
第 2 行 N 个整数表示每棵树的高度。
输出格式
1 个整数，表示锯片的最高高度。
输入输出样例
输入 #1
4 7 20 15 10 17输出 #1
15输入 #2
5 20 4 42 40 26 46输出 #2
36说明/提示
对于 100% 的测试数据，1≤N≤10^6，1≤M≤2×10^9，树的高度 <10^9，所有树的高度总和 >M。
package 高校算法社区每日一题;
import java.io.*;
import java.util.regex.Matcher;
/**
* @author yx
* @date 2022-04-26 20:53
*/
public class 洛谷P1873砍树__二分__快读 {
static int n=1000010;
static int[] tree=new int[n];
static int N;
static long M;
//快读模板
static class Reader {
public BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public StreamTokenizer st = new StreamTokenizer(br);
public void token() {
try {
st.nextToken();
} catch (IOException e) {}
}
public int nextInt() {
token();
return (int)st.nval;
}
public String next() {
token();
return st.sval;
}
}
public static void main(String[] args) {
Reader sc=new Reader();
N=sc.nextInt();
M=sc.nextInt();
int left=0;
int right=0;
for (int i = 1; i <=N ; i++) {
tree[i]=sc.nextInt();
right= Math.max(right,tree[i]);
}
while (left<right){
//自己一步步推导一下
int mid=(left+right+1)>>1;//(r+l+1)中的+1是为了防治死循环
if(check(mid)>=M){
left=mid;
}else{
right=mid-1;
}
}
System.out.println(left);
}
static long check(int mid){
long sum=0;
for (int i = 1; i <=N ; i++) {
if(tree[i]>mid){
sum+=(tree[i]-mid);
}
}
return sum;
}
}
💐题解分析：
1、使用快读模板，减少读取数据所损耗的时间，这个大家可以拿一个小本本给记下来
2、继续老样子，定义左指针右指针和中间值，分别是left、right、mid
3、check（）函数对木材进行求和
4、check和if的结合，相当于一个方向标去告诉左右指针接下来应该如何操作
💐难点分析：
1、灵活使用快读模板
2、
int mid=(left+right+1)>>1;//(r+l+1)中的+1是为了防治死循环向上取整防止死循环
🚀写在最后
最近有点迷，经常性迷茫可能是当代大学生的通病吧，大学的前两年过的很累，但也充实，emm，做过很多尝试，打过很多比赛，时间过的很紧凑，仿佛每天都在忙碌，但似乎留给自己去思考的时间并不是很多，在接下来大学的后两年生活里，我想卸下一些担子，全身心去做自己真正想做的事情，而不是陷入无限的内耗，正值年少风华正茂，我们不应该被束缚！
送给一些正处于迷茫期的朋友一段话吧：
生活不是处处都能如你所愿，正所谓人生不如意之十有八九，心烦的时候去听听歌，去打打球，去练练字，去见想见的人，去看那些还没有看过的书！
（今天二分就讲了两道适合入门的题目，大家如果感兴趣可以去洛谷上可以多多练习类似的题目，如果文章内容对你有所帮助，希望能三连支持一下，非常感谢）
相关文章
