二分答案——木材加工(洛谷 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
上一篇: 非法收购、加工红豆杉制品 获刑一 |
下一篇: 罗汉松和红豆杉的区别,分别怎么养 |
推荐分享

- 1君子兰什么品种最名贵 十大名 4012
- 2世界上最名贵的10种兰花图片 3364
- 3花圈挽联怎么写? 3286
- 4迷信说家里不能放假花 家里摆 1878
- 5香山红叶什么时候红 1493
- 6花的意思,花的解释,花的拼音 1210
- 7教师节送什么花最合适 1167
- 8勿忘我花图片 1103
- 9橄榄枝的象征意义 1093
- 10洛阳的市花 1039