**Method:**\n1. left - inclusive; right - exclusive\n2. use while left < right\n3. if finding min value, define \'isok\' function (and return left) ; \n4. if finding max value, define \'isfail\' function (and return left-1).\n\nIn Chinese:\n\n1. \u5DE6\u95ED\u53F3\u5F00\uFF1B\n2. \u4F7F\u7528left < right\n3. binary search\u662F\u7528\u6765\u67E5\u627E\u6700\u5C0F\u503C\u7684\uFF0C\u5982\u679C\u9898\u76EE\u662F\u5BFB\u627E\u6700\u5C0F\u503C\uFF0C\u90A3\u5C31\u76F4\u63A5\u8FD4\u56DEleft\uFF1B\n4. \u5982\u679C\u9898\u76EE\u8981\u6C42\u7684\u662F\u6700\u5927\u503C\uFF0C\u90A3\u5B9A\u4E49\u4E00\u4E2Aisfail\u51FD\u6570\uFF0C\u5E76\u627E\u8BA9isfail\u8FD4\u56DEtrue\u7684\u6700\u5C0F\u7684left\uFF0C\u8FD9\u6837\u7684\u8BDD\uFF0Cleft-1\u5C31\u662F\u6211\u4EEC\u8981\u6C42\u7684\u6700\u5927\u7684\u6EE1\u8DB3\u6761\u4EF6\u7684\u503C\u4E86\u3002\n\n\n**1231. Divide Chocolate**\n\nHard\nhttps://leetcode.com/problems/divide-chocolate/\n\nYou have one chocolate bar that consists of some chunks. Each chunk has its own sweetness given by the array sweetness.\n\nYou want to share the chocolate with your K friends so you start cutting the chocolate bar into K+1 pieces using K cuts, each piece consists of some consecutive chunks.\n\nBeing generous, you will eat the piece with the minimum total sweetness and give the other pieces to your friends.\n\nFind the maximum total sweetness of the piece you can get by cutting the chocolate bar optimally.\n\nExample 1:\n\nInput: sweetness = [1,2,3,4,5,6,7,8,9], K = 5\nOutput: 6\nExplanation: You can divide the chocolate to [1,2,3], [4,5], [6], [7], [8], [9]\n\n```\n# point: looking for max value, then build a "fail" function,\n# and use binary search to find the min \'left\' that let fail(left) return True.\n# then, left-1 is the max value to let fail(left-1) return False (i.e., not_fail(left-1) is true)!\nclass Solution_Leetcode1231(object):\n def maximizeSweetness(self, sweetness, K):\n # binary search method is for looking for the MIN value! so, we find the min value (left) that fail\n # then left-1 is the max value that success!\n # look for max value, find the min value that fail, and then min.value - 1 is the result of success\n \n left = min(sweetness)\n right = sum(sweetness)+ 1\n \n def fail(mid):\n pieces = 0\n cursum = 0\n for sweet in sweetness:\n cursum += sweet\n if cursum >= mid:\n # then current piece is ensure to be >= mid, we can start a new piece\n pieces += 1\n cursum = 0\n return pieces < K+1\n \n while left < right:\n mid = left+ (right-left)//2\n if fail(mid): # the result \'left\' is the min value that let fail(left)=True!\n right = mid\n else:\n left = mid + 1\n return left - 1\n``` \n\nhttps://leetcode.com/problems/split-array-largest-sum/\n**410. Split Array Largest Sum**\n\nHard\nGiven an array nums which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays.\n\nWrite an algorithm to minimize the largest sum among these m subarrays.\n\nExample 1:\n\nInput: nums = [7,2,5,10,8], m = 2\nOutput: 18\nExplanation:\nThere are four ways to split nums into two subarrays.\nThe best way is to split it into [7,2,5] and [10,8],\nwhere the largest sum among the two subarrays is only 18.\n\'\'\'\n```\n# looking for a min value, then build a \'isok\' function and directly use binary search,\n# to find the min value \'left\' so that ok(left) returns True!\nclass Solution_leetcode410(object):\n def splitArray(self, nums, m):\n # binary search\n # make a guess and then check how many subarrays x; if x > m, the guess is too big; else, the guess is too small\n left = max(nums)\n right = sum(nums) + 1\n \n def isok(mid): # or, you can change \'isok\' name into \'is_mid_too_big\'\n # all subarray\'s sum <= mid\n setcount = 1\n cursum = 0\n for num in nums:\n if cursum + num> mid:\n setcount += 1\n cursum = 0\n cursum += num\n return setcount <= m # this is <=, not >=! which is very important!\n \n while left < right:\n mid = left + (right - left) // 2\n if isok(mid): # is_mid_too_big, and we do not have enough subset when separating under mid, so we should make mid smaller!\n # or, think extremelly, if mid=2**31-1, then all numbers are in one subset, 1 <= m, so we should make mid smaller!\n right = mid\n else:\n left = mid + 1\n return left\n\nclass Solution_leetcode410_2(object):\n def splitArray(self, nums, m):\n # use binary search - it is finding the min value!\n # find the min sum value such that for the m sbusets of nums, sum of a subset <= x\n \n left = max(nums)\n right = sum(nums)\n \n def subsetnum(mid):\n setnum = 1\n cursum = 0\n for num in nums:\n if cursum + num > mid: # \u8F6C\u6362\u601D\u60F3\uFF1A\u672C\u6765\u662F\u7ED9\u5B9Am\u4E2A\u5B50\u96C6\uFF0C\u6C42\u5F97\u662F\u5B50\u96C6\u548C\u5F97\u6700\u5927\u503C\u3002\n\t\t\t\t\t# \u6211\u4EEC\u53CD\u8FC7\u6765\uFF0C\u5148\u6307\u5B9A\u5B50\u96C6\u7684\u548C\u7684\u6700\u5927\u503C\uFF0C\u7136\u540E\u53BB\u53CD\u63A8\u80FD\u80FD\u591F\u5206\u6210\u591A\u5C11\u4E2A\u5B50\u96C6\n # \u5982\u679C\u5B50\u96C6\u7684\u4E2A\u6570>m\uFF0C\u8BF4\u660E\u6211\u4EEC\u7684\u731C\u6D4B\u592A\u5C0F\u4E86\n # \u5982\u679C\u5B50\u96C6\u7684\u4E2A\u6570< m, \u8BF4\u660E\u6211\u4EEC\u7684\u731C\u6D4B\u592A\u5927\u4E86\n\t\t\t\t\t# \uFF08\u8003\u8651\u731C\u6D4B\u4E3A\u65E0\u7A77\u5927\u7684\u65F6\u5019\uFF0C\u6211\u4EEC\u53EA\u9700\u8981\u4E00\u4E2Asubset\u5C31\u53EF\u4EE5\u4E86\uFF09=\u4E5F\u5C31\u662F\u8BF4\uFF0C\u731C\u6D4B\u592A\u5927\u4E86\uFF0C\u6211\u4EEC\u9700\u8981\u53D8\u5C0F\u5B83\n setnum += 1\n cursum = 0\n cursum += num\n return setnum\n \n while left < right:\n mid = left + (right - left) // 2\n if subsetnum(mid) <= m: # \u8BF4\u660E\u6211\u4EEC\u7684\u731C\u6D4B\u592A\u5927\u4E86\uFF01\u6211\u4EEC\u9700\u8981\u51CF\u5C0Fmid! \u8FD9\u4E00\u70B9\u975E\u5E38\u91CD\u8981!\n # extremely, if we guess mid = 2**31-1, then subsetnum(mid) = 1 \n\t\t\t\t# (all elements are in one subset), this means that our guessing is too big\n # we can make it smaller!\n right = mid\n else:\n left = mid + 1\n return left\n```\n\n\'\'\'\n**1011. Capacity To Ship Packages Within D Days**\n\nMedium\nhttps://leetcode.com/problems/capacity-to-ship-packages-within-d-days/\nShare\nA conveyor belt has packages that must be shipped from one port to another within D days.\n\nThe i-th package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.\n\nReturn the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within D days.\n\nExample 1:\n\nInput: weights = [1,2,3,4,5,6,7,8,9,10], D = 5\nOutput: 15\nExplanation: \nA ship capacity of 15 is the minimum to ship all the packages in 5 days like this:\n1st day: 1, 2, 3, 4, 5\n2nd day: 6, 7\n3rd day: 8\n4th day: 9\n5th day: 10\n\nNote that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed. \n\'\'\'\n\n```\n# # looking for a min value, then build a \'isok\' function and directly use binary search to \n# find the min value \'left\' so that ok(left) returns True!\nclass Solution_leetcode1011:\n def shipWithinDays(self, weights, D):\n # binary search\n # min weight capacity of the ship\n \n def isok(mid):\n # real days needed with max weight capacity of mid\n day = 1\n cursum = 0\n for weight in weights:\n if cursum + weight > mid:\n day += 1\n cursum = 0\n cursum += weight\n return day <= D\n \n left = max(weights) # note that this should be max(weights), not min(weights)!!\n right = sum(weights) + 1\n while left < right:\n mid = left + (right - left) // 2\n if isok(mid):\n right = mid\n else:\n left = mid + 1\n return left\n```\n\n\n**1482. Minimum Number of Days to Make m Bouquets**\n\nhttps://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/\nGiven an integer array bloomDay, an integer m and an integer k.\n\nWe need to make m bouquets. To make a bouquet, you need to use k adjacent flowers from the garden.\n\nThe garden consists of n flowers, the ith flower will bloom in the bloomDay[i] and then can be used in exactly one bouquet.\n\nReturn the minimum number of days you need to wait to be able to make m bouquets from the garden. If it is impossible to make m bouquets return -1.\n\'\'\'\n```\nclass Solution_Leetcode1482:\n def minDays(self, bloomdays, m, k):\n # binary search method, seek for the min day, \n # guess a day, -> check how many bouquets \u82B1\u675F\n \n left = min(bloomdays)\n right = max(bloomdays) + 1\n \n def isgood(mid):\n count = 0\n cursum = 0\n for aday in bloomdays:\n if aday > mid:\n cursum = 0 # reset to 0\n else:\n cursum += 1\n if cursum == k:\n count += 1\n cursum = 0 # need to reset cursum here!\n return count >= m\n \n while left < right:\n mid = left + (right - left) // 2\n if isgood(mid):\n right = mid\n else:\n left = mid + 1\n return left if left <= max(bloomdays) else -1\n```\n\n\n**875. Koko Eating Bananas**\nhttps://leetcode.com/problems/koko-eating-bananas/\n\nKoko 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.\n\nKoko 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.\n\nKoko likes to eat slowly, but still wants to finish eating all the bananas before the guards come back.\n\nReturn the minimum integer K such that she can eat all the bananas within H hours.\n```\n\nclass Solution_leetcode875(object):\n def minEatingSpeed(self, piles, H):\n # still, change the problem, binary search,\n # guess the target value and compute how many banana koko can eat -> min speed\n left = 1\n right = max(piles) + 1\n \n def caneatall(mid): # isok(mid)\n # hours cost really should <=H\n hours = 0\n for pile in piles:\n hours += math.ceil(pile/float(mid)) \n # do not work if we use pile/mid!!! should change int into float!! this is very important!\n return hours <= H\n \n while left < right:\n mid = left + (right - left)//2\n if caneatall(mid):\n right = mid\n else:\n left = mid + 1\n return left # the min speed that satisfies caneatall(left)\n```\n\n\nGo back to finding max value again, using binary search!\n\n**1552. Magnetic Force Between Two Balls**\nhttps://leetcode.com/problems/magnetic-force-between-two-balls/\n\nIn universe Earth C-137, Rick discovered a special form of magnetic force between two balls if they are put in his new invented basket. Rick has n empty baskets, the ith basket is at position[i], Morty has m balls and needs to distribute the balls into the baskets such that the minimum magnetic force between any two balls is maximum.\n\nRick stated that magnetic force between two different balls at positions x and y is |x - y|.\n\nGiven the integer array position and the integer m. Return the required force.\n```\nclass Solution_Leetcode1552:\n def maxDistance(self, position, m):\n n = len(position)\n position.sort()\n \n def isfail(mid):\n ans = 1\n curr = position[0] # alike greedy idea, we just put the first ball at position 0!\n for i in range(1, n):\n if position[i] - curr >= mid:\n ans += 1\n curr = position[i]\n return ans < m\n \n left = 0 # \u6CE8\u610F\uFF0C\u4E0D\u5E94\u8BE5\u628Aleft\u8D4B\u503C\u4E3Amin(position)! \u56E0\u4E3A\u6211\u4EEC\u6C42\u5F97\u662Fdistance!\n # note that, left = min(position) is wrong, since we are looking for \'distance\'!\n right = max(position) - min(position) + 1\n while left < right:\n mid = left + (right - left) // 2\n if isfail(mid):\n right = mid\n else:\n left = mid + 1\n return left - 1 # left is the min value to fail, so left-1 is the max value to succeed!\n # \u56E0\u4E3A\u6C42\u7684\u662F\u6700\u5927\u503C\uFF01\u6240\u4EE5\u9700\u8981\u5DE7\u5999\u4F7F\u7528binary search!\n```

Divide Chocolate

Problem Description

Problem Description

Answer Panel