2024-12-16：使数组中所有元素相等的最小开销。用go语言，给定一个整数数组 nums 以及两个整数 cost1 和 cost2，你可以进行以下两种操作多次：

1.选择数组中的某个元素的下标 i，将 nums[i] 增加 1，花费为 cost1。

2.同时选择数组中两个不同的下标 i 和 j，将 nums[i] 和 nums[j] 都增加 1，花费为 cost2。

你的目标是使数组中的所有元素相等，求达成此目标所需的最小总开销。由于结果可能很大，请将结果对 1000000007 取模后返回。

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

输出：15 。

解释：

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

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

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

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

总开销为 15 。

答案2024-12-16：

chatgpt

题目来自leetcode3139。

大体步骤如下：

1.初始化变量 mod 为 1_000_000_007，表示取模值。

2.计算数组 nums 的长度 n，以及数组中的最小值 m 和最大值 M。

3.计算基准值 base，初始值为每个元素的和乘以最大值 M 减去所有元素的和，即 n*M - Σ(nums)。

4.检查特殊情况：若数组大小小于等于 2 或者 cost1 的两倍小于等于 cost2，则直接返回基准值乘以 cost1 取模后的结果。

5.定义函数 f(x)，根据提供的计算规则计算总开销。

6.计算一个关键值 i，根据给定的公式进行计算，用于确定最终结果在哪个范围内。

7.根据 i 和 M 的关系，选择合适的值来计算最小开销，并返回结果。

总体时间复杂度：

• 此算法的时间复杂度取决于遍历数组和执行各种计算操作，为 O(n)。

总体额外空间复杂度：

• 算法中使用了一些常量空间来存储变量和常量值，以及 map 数据结构用于存储计数，因此额外空间复杂度为 O(1)。

Go完整代码如下：

package main

import (
	"fmt"
	"slices"
)

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
}

func main() {
	nums := []int{4, 1}
	cost1 := 5
	cost2 := 2
	fmt.Println(minCostToEqualizeArray(nums, cost1, cost2))
}

Rust完整代码如下：

use std::cmp;

fn min_cost_to_equalize_array(nums: &Vec<i32>, c1: i32, c2: i32) -> i32 {
    const MOD: i32 = 1_000_000_007;
    let n = nums.len();
    let m = *nums.iter().min().unwrap();
    let M = *nums.iter().max().unwrap();
    let mut base = n as i32 * M;

    for x in nums {
        base -= x;
    }

    if n <= 2 || c1 * 2 <= c2 {
        return (base * c1) % MOD;
    }

    let f = |x: i32| -> i32 {
        let s = base + (x - M) * n as i32;
        let d = x - m;
        if d * 2 <= s {
            return s / 2 * c2 + s % 2 * c1;
        } else {
            return (s - d) * c2 + (d * 2 - s) * c1;
        }
    };

    let i = (n as i32 * M - m * 2 - base + n as i32 - 3) / (n as i32 - 2);

    if i <= M {
        return cmp::min(f(M), f(M + 1)) % MOD;
    } else {
        let min_f = cmp::min(f(M), cmp::min(cmp::min(f(i - 1), f(i)), f(i + 1))) % MOD;
        return min_f;
    }
}

fn main() {
    let nums = vec![4, 1];
    let cost1 = 5;
    let cost2 = 2;
    println!("{}", min_cost_to_equalize_array(&nums, cost1, cost2));
}