Menu Sidebar
Menu

Archive: February 24, 2021

Minimum Limit of Balls in a Bag

给一个数组, 问如何通过maxOperations个操作, 让数字中最大数字变得最小, 操作是把一个数分割成两个数字的和. 这个题上来肯定用优先队列来一个个找最大的数, 然后分, 但是这里有个问题是, 如何分才能在给出的maxOperations的操作下, 确保最小, 这个策略比较难定. 于是换个思路: 在maxOperations个操作下, 如果结果得到的数字中最大的数字是x, 那么x+1也可以, 所以可以用二分搜索找lower bound.

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.