csp信奥赛C++高频考点专项训练：【二分答案】案例2：木材加工

csp信奥赛C高频考点专项训练【二分答案】案例2木材加工题目描述木材厂有n nn根原木现在想把这些木头切割成k kk段长度均为l ll的小段木头木头有可能有剩余。当然我们希望得到的小段木头越长越好请求出l ll的最大值。木头长度的单位是cm \text{cm}cm原木的长度都是正整数我们要求切割得到的小段木头的长度也是正整数。例如有两根原木长度分别为11 1111和21 2121要求切割成等长的6 66段很明显能切割出来的小段木头长度最长为5 55。输入格式第一行是两个正整数n , k n,kn,k分别表示原木的数量需要得到的小段的数量。接下来n nn行每行一个正整数L i L_iLi​表示一根原木的长度。输出格式仅一行即l ll的最大值。如果连1cm \text{1cm}1cm长的小段都切不出来输出0。输入输出样例 1输入 13 7 232 124 456输出 1114说明/提示对于100 % 100\%100%的数据有1 ≤ n ≤ 10 5 1\le n\le 10^51≤n≤1051 ≤ k ≤ 10 8 1\le k\le 10^81≤k≤1081 ≤ L i ≤ 10 8 ( i ∈ [ 1 , n ] ) 1\le L_i\le 10^8(i\in[1,n])1≤Li​≤108(i∈[1,n])。AC代码#includebits/stdc.husingnamespacestd;constintN1e510;intn,k,a[N],ans;// ans保存最终结果初始为0符合题目要求的无法切割情况输出0// 检查能否将原木切割成至少k段每段长度为xboolcheck(intx){intcnt0;for(inti1;in;i){cnta[i]/x;// 当前原木可切割出的段数}returncntk;// 总段数是否满足需求}intmain(){cinnk;for(inti1;in;i)cina[i];intl1,r1e8,mid;// 二分查找的初始左右边界最大可能长度为1e8// 二分查找寻找最大可行长度while(lr){mid(lr)/2;if(check(mid)){// 当前长度可行尝试更大的长度ansmid;// 更新答案lmid1;}else{// 当前长度不可行减小长度rmid-1;}}coutans;// 输出结果若无法切割则为初始值0return0;}功能分析该程序使用二分查找算法确定能够切割出k段等长木头的最大可能长度。具体步骤如下输入处理读取原木数量n和目标段数k以及每根原木的长度。二分查找初始化设定初始左边界为1最小可能长度右边界为1e8最大可能长度。检查函数check计算给定长度x下所有原木能切割出的总段数判断是否满足至少k段的需求。二分过程不断调整左右边界寻找满足条件的最大长度。若当前中间值可行则尝试更大的长度否则减小长度。结果输出最终输出找到的最大长度若无法满足条件则输出初始值0。该算法高效处理了大范围数据时间复杂度为O(n log(maxL))适用于题目给定的数据规模。完整信奥赛C普及组CSP-J一等奖通关刷题题单及题解请关注专栏https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}