招行信用卡中心提前批笔试第三题

贪心+二分

贪心策略：直接求出 s 分裂 k 次的最大增益。

s分k次会产生 k+1 个数越均分越大

例 15 分裂 3 次会产生四个数越均分越大他们是 4,4,4,3

最大增益 = 4*11+4*7+4*3

最多分为 s-1次，

所以进行【0，s-1】区间上的二分。

class Solution:
    def minCount(self, s:int, m:int):
        '''
        拆分 s 使其增益大于等于 m 的最小拆分次数
        方法一： 纯贪心+二分
        '''
        times = s-1 # 贪心求出最多分的次数

        def computProduct(mid, s):
            base = s // (mid + 1)
            remain = s % (mid + 1)

            split = s
            product = 0

            for _ in range(remain):
                split -= (base + 1)
                product += (base + 1) * split

            for _ in range(mid + 1 - remain):
                split -= base
                product += base * split

            return product

        def biSearch(left, right):
            while left<right:
                mid = left + (right - left) // 2  # 分 mid 次

                if computProduct(mid, s)>=m:
                    right = mid
                else:
                    left = mid+1

            return left if computProduct(left, s)>=m else -1

        return biSearch(0, times)