二分答案——木材加工(洛谷 P2440)

题目选自洛谷P2440

读完题目后应该有个大致思路，看得出来是二分查找的题。

首先我们输入 n 和 k 并且运用二分找到合适的尺寸，而l 必须要足够小，r 必须要足够的大。题中写道数组中的数最大不会超过 100000000 ，所以我们设 100000001 就可以了。

现在就走到了判断的环节，我们如何判断 mid 是太小还是太大呢？我们需要编写一个新函数 --------check。

在函数 check中，我们依次要判断 a 中的每一个数并计算出能切出多少个 mid ，还要用一个变量 num 储存他们，如果 num 分的分数比 k 多或者正好等于，返回真。如果是小于 k ，返回假。

当 check 返回的是真的时候，我们就要试试还能不能把 mid 调大一点，就要

l = mid;

如果返回的是假，我们就加的太大了，就要把 mid 调小一点，就要

r = mid;

一直到结束，输出 l 就可以了。

 其实最长的长度不会超过里面最长的一根的长度，可以先将长度排序，然后找到最长的，就是r初值，这样也可以减少一些判断。

题目背景

要保护环境

题目描述

木材厂有 n 根原木，现在想把这些木头切割成 k 段长度均为 l 的小段木头（木头有可能有剩余）。

当然，我们希望得到的小段木头越长越好，请求出 ll 的最大值。

木头长度的单位是 cm，原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。

例如有两根原木长度分别为 11 和 21，要求切割成等长的 6 段，很明显能切割出来的小段木头长度最长为 5。

输入格式

第一行是两个正整数 n,k，分别表示原木的数量，需要得到的小段的数量。

接下来 n 行，每行一个正整数Li​，表示一根原木的长度。

输出格式

仅一行，即 ll 的最大值。

如果连 1cm 长的小段都切不出来，输出 0。

输入输出样例

输入 1

3 7 232 124 456

输出 1

114

解题代码： 

#include<stdio.h>

#include<iostream>

using namespace std;

int n,k,maxl;

int a[100010];

bool check(int ml){

int num = 0;

for(int i=0;i<n;i++){

num += a[i] / ml;

if(num >= k) return true;

}

return false;

}

int main(){

cin>>n>>k;

for(int i=0;i<n;i++)

cin>>a[i];

int l=0,r=100000001;

while(l+1<r){

maxl=(l+r)/2;

if(check(maxl)) l=maxl;

else r=maxl;

}

cout<<l;

return 0;

}

相关知识

洛谷 P1077 摆花 题解
木材价格
“木材”字的解释
木材的环保与碳汇效应考核试卷.docx
攀枝花市开展木材市场联合检疫执法检查
咏洛赋
废木材粉碎哪里回收
常用的花园景观木材有哪些
组队赛8：Journey to the “The World's Start” 二分+单调队列优化dp
探秘鸡丝木——一种珍贵的木材资源（来源）

网址: 二分答案——木材加工(洛谷 P2440) https://www.huajiangbk.com/newsview896908.html