使数组中所有元素相等的最小开销

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

给你一个整数数组 nums 和两个整数 cost1 和 cost2 。你可以执行以下任一操作任意次：

从 nums 中选择下标 i 并且将 nums[i] 增加 1 ，开销为 cost1。
选择 nums 中两个不同下标 i 和 j ，并且将 nums[1] 和 nums[2] 都增加 1 ，开销为 cost2 。

你的目标是使数组中所有元素都相等，请你返回需要的 最小开销 之和。

由于答案可能会很大，请你将它对 10⁹ + 7 取余后返回。

示例 1：

输入：nums = [4,1], cost1 = 5, cost2 = 2

输出：15

解释：

执行以下操作可以使数组中所有元素相等：

将 nums[1] 增加 1 ，开销为 5 ，nums 变为 [4,2] 。
将 nums[1] 增加 1 ，开销为 5 ，nums 变为 [4,3] 。
将 nums[1] 增加 1 ，开销为 5 ，nums 变为 [4,4] 。

总开销为 15 。

示例 2：

输入：nums = [2,3,3,3,5], cost1 = 2, cost2 = 1

输出：6

解释：

执行以下操作可以使数组中所有元素相等：

将 nums[0] 和 nums[1] 同时增加 1 ，开销为 1 ，nums 变为 [3,4,3,3,5] 。
将 nums[0] 和 nums[2] 同时增加 1 ，开销为 1 ，nums 变为 [4,4,4,3,5] 。
将 nums[0] 和 nums[3] 同时增加 1 ，开销为 1 ，nums 变为 [5,4,4,4,5] 。
将 nums[1] 和 nums[2] 同时增加 1 ，开销为 1 ，nums 变为 [5,5,5,4,5] 。
将 nums[3] 增加 1 ，开销为 2 ，nums 变为 [5,5,5,5,5] 。

总开销为 6 。

示例 3：

输入：nums = [3,5,3], cost1 = 1, cost2 = 3

输出：4

解释：

执行以下操作可以使数组中所有元素相等：

将 nums[0] 增加 1 ，开销为 1 ，nums 变为 [4,5,3] 。
将 nums[0] 增加 1 ，开销为 1 ，nums 变为 [5,5,3] 。
将 nums[2] 增加 1 ，开销为 1 ，nums 变为 [5,5,4] 。
将 nums[2] 增加 1 ，开销为 1 ，nums 变为 [5,5,5] 。

总开销为 4 。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁶
1 <= cost1 <= 10⁶
1 <= cost2 <= 10⁶

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int minCostToEqualizeArray(vector<int>& nums, int cost1, int cost2) { } };

golang 解法, 执行用时: 84 ms, 内存消耗: 8.7 MB, 提交时间: 2024-05-06 10:19:03

// 分类讨论
func minCostToEqualizeArray(nums []int, c1 int, c2 int) int {
	const mod = 1_000_000_007
	n := len(nums)
	m := slices.Min(nums)
	M := slices.Max(nums)
	base := n * M
	for _, x := range nums {
		base -= x
	}
	if n <= 2 || c1*2 <= c2 {
		return base * c1 % mod
	}

	f := func(x int) int {
		s := base + (x-M)*n
		d := x - m
		if d*2 <= s {
			return s/2*c2 + s%2*c1
		}
		return (s-d)*c2 + (d*2-s)*c1
	}

	i := (n*M - m*2 - base + n - 3) / (n - 2)
	if i <= M {
		return min(f(M), f(M+1)) % mod
	}
	return min(f(M), f(i-1), f(i), f(i+1)) % mod
}

python3 解法, 执行用时: 70 ms, 内存消耗: 30.6 MB, 提交时间: 2024-05-06 10:18:52

class Solution:
    def minCostToEqualizeArray(self, nums: List[int], c1: int, c2: int) -> int:
        MOD = 1_000_000_007
        n = len(nums)
        m = min(nums)
        M = max(nums)
        base = n * M - sum(nums)
        if n <= 2 or c1 * 2 <= c2:
            return base * c1 % MOD

        def f(x: int) -> int:
            s = base + (x - M) * n
            d = x - m
            if d * 2 <= s:
                return s // 2 * c2 + s % 2 * c1
            return (s - d) * c2 + (d * 2 - s) * c1

        i = (n * M - m * 2 - base + n - 3) // (n - 2)
        return min(f(M), f(M + 1)) % MOD if i <= M else \
               min(f(M), f(i - 1), f(i), f(i + 1)) % MOD

java 解法, 执行用时: 1 ms, 内存消耗: 56.1 MB, 提交时间: 2024-05-06 10:18:41

class Solution {
    public int minCostToEqualizeArray(int[] nums, int c1, int c2) {
        final int MOD = 1_000_000_007;
        long n = nums.length;
        int m = Integer.MAX_VALUE;
        int M = Integer.MIN_VALUE;
        long sum = 0;
        for (int x : nums) {
            m = Math.min(m, x);
            M = Math.max(M, x);
            sum += x;
        }

        long base = n * M - sum;
        if (n <= 2 || c1 * 2 <= c2) {
            return (int) (base * c1 % MOD);
        }

        int i = (int) ((n * M - m * 2 - base + n - 3) / (n - 2));
        long res1 = f(M, base, n, m, M, c1, c2);
        long res2 = f(M + 1, base, n, m, M, c1, c2);
        long res3 = f(i - 1, base, n, m, M, c1, c2);
        long res4 = f(i, base, n, m, M, c1, c2);
        long res5 = f(i + 1, base, n, m, M, c1, c2);
        return (int) (i <= M ? Math.min(res1, res2) % MOD :
                Math.min(Math.min(Math.min(res1, res3), res4), res5) % MOD);
    }

    private long f(int x, long base, long n, int m, int M, int c1, int c2) {
        long s = base + (x - M) * n;
        int d = x - m;
        if (d * 2 <= s) {
            return s / 2 * c2 + s % 2 * c1;
        }
        return (s - d) * c2 + (d * 2 - s) * c1;
    }
}

cpp 解法, 执行用时: 113 ms, 内存消耗: 90.8 MB, 提交时间: 2024-05-06 10:18:27

class Solution {
public:
    int minCostToEqualizeArray(vector<int>& nums, int c1, int c2) {
        const int MOD = 1'000'000'007;
        long long n = nums.size();
        auto [m, M] = ranges::minmax(nums);
        long long base = n * M - reduce(nums.begin(), nums.end(), 0LL);
        if (n <= 2 || c1 * 2 <= c2) {
            return base * c1 % MOD;
        }

        auto f = [&](int x) -> long long {
            long long s = base + (x - M) * n;
            int d = x - m;
            if (d * 2 <= s) {
                return s / 2 * c2 + s % 2 * c1;
            }
            return (s - d) * c2 + (d * 2 - s) * c1;
        };

        int i = (n * M - m * 2 - base + n - 3) / (n - 2);
        return i <= M ? min(f(M), f(M + 1)) % MOD :
               min({f(M), f(i - 1), f(i), f(i + 1)}) % MOD;
    }
};

上一题

下一题

详情