# On a horizontal number line, we have gas stations at positions stations[0], stations[1], ..., stations[N-1],
# where N = stations.length.
#
# Now, we add K more gas stations so that D, the maximum distance between adjacent gas stations, is minimized.
#
# Return the smallest possible value of D.
#
# Example:
#
# Input: stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], K = 9
# Output: 0.500000
# Note:
#
# stations.length will be an integer in range [10, 2000].
# stations[i] will be an integer in range [0, 10^8].
# K will be an integer in range [1, 10^6].
# Answers within 10^-6 of the true value will be accepted as correct.
import heapq
import math


# https://youtu.be/N_iCpjc4xIo

class Solution(object):
    def minmaxGasDist_wrong(self, stations, K):
        """
        :type stations: List[int]
        :type K: int
        :rtype: float
        """
        n = len(stations)
        gaps = [0] * (n - 1)
        for i in xrange(1, n):
            gaps[i - 1] = stations[i] - stations[i - 1]

        t, r = K / (n - 1), K % (n - 1)

        arr = [(-v * 1.0 / (1 + t), v, 1 + t) for v in gaps]
        heapq.heapify(arr)

        while r:
            interval, total, points = heapq.heappop(arr)
            heapq.heappush(arr, (float("{0:.6f}".format(-total * 1.0 / (points + 1))), total, points + 1))
            r -= 1

        return float("{0:.6f}".format(abs(heapq.heappop(arr)[0])))

    def minmaxGasDist(self, stations, K):
        """
        :type stations: List[int]
        :type K: int
        :rtype: float
        """
        n = len(stations)
        baseGap, gaps = (stations[-1] - stations[0] + 1) * 1.0 / (1 + K), []

        for i in xrange(n - 1):
            points = max(1, int((stations[i + 1] - stations[i]) / baseGap))
            K -= (points - 1)
            gaps.append(((stations[i] - stations[i + 1]) * 1.0 / points, stations[i], stations[i + 1], points - 1))

        heapq.heapify(gaps)

        while K:
            interval, a, b, points = heapq.heappop(gaps)
            heapq.heappush(gaps, ((a - b) * 1.0 / (points + 2), a, b, points + 1))
            K -= 1

        return float("{0:.6f}".format(abs(heapq.heappop(gaps)[0])))

    def minmaxGasDist3(self, stations, K):
        """
        :type stations: List[int]
        :type K: int
        :rtype: float
        """
        n = len(stations)
        baseGap, gaps = (stations[-1] - stations[0] + 1) * 1.0 / (1 + K), []

        for i in xrange(n - 1):
            points = max(1, int((stations[i + 1] - stations[i]) / baseGap))
            K -= (points - 1)
            gaps.append(((stations[i] - stations[i + 1]) * 1.0 / points, stations[i], stations[i + 1], points))

        heapq.heapify(gaps)

        while K:
            interval, a, b, points = heapq.heappop(gaps)
            heapq.heappush(gaps, ((a - b) * 1.0 / (points + 1), a, b, points + 1))
            K -= 1

        return float("{0:.6f}".format(abs(heapq.heappop(gaps)[0])))

    # binary search
    def minmaxGasDist2(self, stations, K):
        """
        :type stations: List[int]
        :type K: int
        :rtype: float
        """
        left, right = 0, 1e8
        while right - left > 1e-6:
            mid = left + (right - left) * 1.0 / 2
            cnt, n = 0, len(stations)
            for i in xrange(n - 1):
                cnt += int((stations[i + 1] - stations[i]) / mid)

            if cnt <= K:
                right = mid
            else:
                left = mid

        return float("{0:.6f}".format(left))

    def minmaxGasDist4(self, stations, K):
        """
        :type stations: List[int]
        :type K: int
        :rtype: float
        """
        left, right = 0, stations[-1] - stations[0]
        while right - left > 1e-6:
            mid = left + (right - left) * 1.0 / 2
            cnt, n = 0, len(stations)
            for i in xrange(n - 1):
                cnt += math.ceil((stations[i + 1] - stations[i]) / mid) - 1

            if cnt <= K:
                right = mid
            else:
                left = mid

        return left



if __name__ == '__main__':
    print Solution().minmaxGasDist([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 9)
    print Solution().minmaxGasDist2([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 9)
    print Solution().minmaxGasDist4([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 9)
    print Solution().minmaxGasDist([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 18)
    print Solution().minmaxGasDist2([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 18)
    print Solution().minmaxGasDist4([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 18)
    print Solution().minmaxGasDist([3, 6, 12, 19, 33, 44, 67, 72, 89, 95], 2)
    print Solution().minmaxGasDist2([3, 6, 12, 19, 33, 44, 67, 72, 89, 95], 2)
    print Solution().minmaxGasDist4([3, 6, 12, 19, 33, 44, 67, 72, 89, 95], 2)
