【每日一题】4月17日题目精讲 二分

题号 NC23049
名称 华华给月月准备礼物
来源 牛客小白月赛12
戳我进入往期每日一题汇总贴~
往期每日一题题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情

直接算显然不现实，我们可以考虑枚举答案验证——从大到小枚举最终的木棍长度，判断是不是所有的原来的木棍都切成这个长度之后够不够K，当枚举到第一个可以的长度的时候就可以停止了。
通过这个暴力的方法我们可以发现其实可行性关于小棍的长度是“单调的”，即如果我们把答案设为ans，那么当最终的木棍长度小于等于ans就都是可行的，而当其大于ans的时候，就不可行了。有了这样的性质就可以考虑二分了（会二分的同学后面就不用看了）——确定枚举的左界L（初值取1），右界R（初值取最长的那根木棍长度），取区间中点mid，如果mid这个值作为最终的木棍长度可行，就说明小于mid的都可行，答案肯定是mid或者在右边，于是就可以缩小区间的范围了，相反的如果mid不可行，答案肯定在mid左边，这个时候修改r就好。区间变小之后重复这个操作，直到区间为空的时候就已经找到答案了。

看完邓老师的题解，记得去做题提高呀~
欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目4月24日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴