周赛20240505

第四题 100288. 使数组中所有元素相等的最小开销

题目大意：给定一个整数数组 nums 和两个整数 cost1 和 cost2，可以执行两种操作来使数组中所有元素相等：1. 选择某个元素增加1，开销为cost1；2. 选择两个不同的元素同时增加1，开销为cost2。目标是使数组中所有元素相等，返回需要的最小开销之和。

实现思路：首先计算数组中最大值mx和最小值mn，然后计算基础开销base，即将最大值变为最小值所需的开销。然后根据两种操作的开销比较，若cost1*2 <= cost2，则只需考虑将最大值变为最小值的开销，直接返回即可。若cost1*2 > cost2，则需要考虑两种操作的比较，通过二分搜索找到使得总开销最小的情况。具体实现中，定义了函数f(x)，表示将最大值变为x时的总开销，然后在mx的范围内进行二分搜索找到最小总开销。

class Solution:
    def minCostToEqualizeArray(self, nums: List[int], c1: int, c2: int) -> int:
        mod = int(1e9) + 7
        mx = max(nums); mn = min(nums)
        n = len(nums)

        base = mx*n - sum(nums)
        if c1*2 <= c2:
            return base * c1 % mod
        
        def f(x):
            d = x - mn
            s = base + (x-mx) * n
            if d <= s-d:
                return s//2 * c2 + s%2*c1
            return (s-d) * c2 + (d-(s-d)) * c1

        ans = inf

        if mx&1:
            ans = f(mx)
            mx += 1
            base += n
        
        k0 = bisect_left( range(mx), True, mx//2, key = lambda m: f(m*2) < f((m+1)*2) )
        k1 = bisect_left( range(mx), True, mx//2, key = lambda m: f(m*2+1) < f((m+1)*2 + 1) )

        ans = min(ans, f(k0*2), f(k1*2 + 1))

        return ans%mod