[1482] Minimum Number of Days to Make m Bouquets 解题报告
算法
用什么算法
binary search
为什么用这个算法？
给了你一个unsorted list，要你找出m个花束，每个花束有k朵花。list里面每一个数代表花开需要的天数，要你找出最少天数能满足花束的要求。
这实际上是在一个list找满足要求的最小数字。 可以用binary search。我之前根本没想到。但这显然是我的知识漏洞，需要补上。就是说一个unsorted list里面如果要你找出一个满足一定条件的最小数字，你就可以在一个range里面用二分法找。
这个range就是这个list最大值。（从1到这个list里面的最大值）当然，你不需要找出最大值，直接用一个很大的数字就行了，（因为题也说了花开的天数是1<= n<= 1e9）
然后在用一个for loop去判断当前mid 满不满足花束的要求。（mid就是天数，从1到1e9的中间值），如果满足，那么end = mid， 如果不满足start = mid + 1;因为mid已经不满足了。然后while的条件是 (start < end)，这样保证了如果最后一次满足条件的mid 被放到end 上了，你可以在进入while，然后start = mid == end，最后离开while loop的时候保证了你start 就是最小的天数。
[875] koko eating bananas 解题报告
Koko loves to eat bananas. There are N piles of bananas, the i-th pile has piles[i] bananas. The guards have gone and will come back in H hours.
Koko can decide her bananas-per-hour eating speed of K. Each hour, she chooses some pile of bananas, and eats K bananas from that pile. If the pile has less than K bananas, she eats all of them instead, and won't eat any more bananas during this hour.
Koko likes to eat slowly, but still wants to finish eating all the bananas before the guards come back.
Return the minimum integer K such that she can eat all the bananas within H hours.
算法
用什么算法
binary search
为什么用这个算法？
这题也是给了你一个unsorted list, 这里面没个数就代表一堆香蕉，然后你要找一个最小的吃速，在规定时间内帮整个list的香蕉吃完。规定的时间就是看门员回来的时间。这实际上就是变相的二分搜索，因为你要找到符合条件的情况，也就是猜一个数，然后看每堆处以这个数的值，（整除就取n，不整除就是n+1，用一个if判断就好了）他们加起来要小于等于H，也就是管理员离开的时间。如果小于就end = mid；如果大于就说明你设置的速度不够，管理员回来了你还没吃完。那就start = mid + 1（因为你是用mid来除的，所以mid已经考虑过了，就用mid+1）
然后return start 就好了，因为这道题失去最小值，我们while loop 取（start < end )这样结束的时候start 会取到最小值
时空复杂度分析
O（NlogM） M就是这个range的长度，然后N就是list的长度，你在while loop里面二分的时候，每次都要for loop 一边list来判断你当前猜的速度是否满足条件，所以是NlogM。
相关题目有哪些做过的
跟哪个题目比较像？
这道题根1482一摸一样，因为都是给了你一组没有排序的数，然后这组数代表了一个物质，你要找出在给出的条件下最小的数。属于range方法的二分法。
网友评论