竞赛
考级
题意要求我们把木材切割成很多段,使得这个短段尽量的长。 我们切割的段肯定是在[ 0,max{ wood [ i ] } ]中,满足二分的有界性。 由题意显然单调,满足单调性。所以可以使用二分答案求解。 如果发现能切够k段则去右半部分找更大的解,如果发现切不够k段就去左边找可行解。
这道题用二分答案来做: begin为最小分段长度(即为0) end为最大分段长度(即为木段长度总和/分段数) mid为中间值 注意!:当找到符合条件的值后要继续寻找最优解(即符合条件的最大分段长度) 以样例为例: 当值为102时,232/102+124/102+456/102总段数也为7, 需继续寻找,最终值为114
提交答案之后,这里将显示提交结果~