首页 分享 二分答案

二分答案

来源:花匠小妙招 时间:2025-01-13 04:31
目录 P2440木材加工题目描述题意思路数据约束参考代码二分的知识点代码框架

P2440木材加工

题目描述

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

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

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

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

##输入格式

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

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

#输出格式

仅一行,即 l l l 的最大值。

如果连 1cm text{1cm} 1cm 长的小段都切不出来,输出 0。

#样例

#样例输入

3 7 232 124 456 1234

#样例输出

114 1

#提示

#数据规模与约定

对于 100 % 100% 100% 的数据,有 1 ≤ n ≤ 1 0 5 1le nle 10^5 1≤n≤105, 1 ≤ k ≤ 1 0 8 1le kle 10^8 1≤k≤108, 1 ≤ L i ≤ 1 0 8 ( i ∈ [ 1 , n ] ) 1le L_ile 10^8(iin[1,n]) 1≤Li​≤108(i∈[1,n])。

题意

至少分成k段,最大长度是多少

思路

长度最短为0,最长为题目a[i]的最大值。如果从最长开始遍历,然后遍历n个数据。二重循环显然超时。考虑到结果是一段数据里面选,那么可以考虑让二分结果,节约时间(分的段越多,长度越小,满足二分的线性条件)

数据约束

无约束 ,注意数组长度就行

参考代码

#include<bits/stdc++.h> using namespace std; const int N = 1e5+5; int a[N],n,k; bool check(int t);//判断该值是否符合条件 int main() {int ans=0,m=-1;//m存储所有木材的里面的最大值,即最大分发cin>>n>>k;for(int i=0;i<n;i++) {cin>>a[i];if(m<a[i] ) m = a[i];}//开始二分结果int l=1,r= m;while(l<=r){ //不能是l<r 一个也让进 !!!int mid = (l+r)/2; //ans = (l+r)>>1;if(check(mid)){ans = mid; //暂时定一个结果l = mid + 1;//缩小范围}else{r = mid-1;}}cout<<ans; return 0; } bool check(int t){int sum=0;//判断是否有k段for(int i=0;i<n;i++){sum += a[i]/t;}return sum>=k;}

12345678910111213141516171819202122232425262728293031323334

二分的知识点

二分的基本用途是在单调序列或单调函数中做查找操作。因此当问题的答案具有单调性时,就可以通过二分把求解转化
为判定(根据复杂度理论,可知判定的难度小于求解),这使得二分的应用范围变得很广泛。进一步
地,我们还可以通过三分法解决单调函数的极值以及相关问题。

条件:线性条件(越,,,越,,, )/单调性

代码框架

整型代码框架

int L=1,R=n,ans; while(L<=R) { int mid=(L+R)>>1; if(check(mid))ans=mid,L=mid十l; //若满足要求,记下答案,并根据题意缩减范围 else R=mid-1; } return ans 12345678

实型代码框架

double l,r;// jd=0.01(根据题目要求决定精度) double mid; while(fabs(l-r)>jd){ mid=(l+r)/2.0; if(check(mid))r=mid;//不能直接+1 else l=mid; } return l; 123456789

1.二分答案

最小值最大(或是最大值最小)问题,确定答案后,配合贪心、DP等其他算法检验这个答案是否合理,将最优化问题转换为判定性问题

例如: 将长度为n的序列a分成m个等长的段,求所有分法中每个段的最大值是多大?

相关知识

木材加工——二分答案
二分答案——木材加工(洛谷 P2440)
组队赛8:Journey to the “The World's Start” 二分+单调队列优化dp
【二分】求方程的根
二分查找模板
天下三分明月夜的下一句是二分无赖是扬州
“天下三分明月夜,二分无赖是扬州”的意思
六条技术应用好 二分菜地巧安排
2251. 花期内花的数目(cpp内置二分查找)
“天下三分明月夜,二分无赖是扬州。”全诗赏析

网址: 二分答案 https://www.huajiangbk.com/newsview1564364.html

所属分类:花卉
上一篇: 麻城市宇诚木材加工厂 (麻城市白
下一篇: 认识莎木——一种珍稀的木材资源(

推荐分享