2025-06-16：最小数组和。用go语言，你有一个整数数组 nums 和三个整数 k、op1、op2。你可以对数组进行以下

福大大架构师每日一题

发布于 2025-06-16 04:12:12

8100

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

2025-06-16：最小数组和。用go语言，你有一个整数数组 nums 和三个整数 k、op1、op2。你可以对数组进行以下两种操作：

1. 操作1：选择一个元素，将该元素除以2后向上取整。最多能执行 op1 次，每个元素最多执行一次此操作。
2. 操作2：选择一个元素，仅当它的值不少于 k 时，从该元素中减去 k。最多能执行 op2 次，每个元素最多执行一次此操作。

同一个元素可以同时执行这两种操作，但每种操作在该元素上只能使用一次。

你的目标是在进行任意次数操作后，使数组元素之和尽可能小。

请返回此情况下数组元素和的最小值。

1 <= nums.length <= 100。

0 <= nums[i] <= 100000。

0 <= k <= 100000。

0 <= op1, op2 <= nums.length。

输入： nums = [2,8,3,19,3], k = 3, op1 = 1, op2 = 1。

输出： 23。

解释：

对 nums[1] = 8 应用操作 2，使 nums[1] = 5。

对 nums[3] = 19 应用操作 1，使 nums[3] = 10。

结果数组变为 [2, 5, 3, 10, 3]，在应用操作后具有最小可能和 23。

题目来自力扣3366。

解决思路

这个问题可以通过动态规划（DP）来解决。我们需要考虑对每个元素选择是否进行操作1或操作2，同时跟踪剩余的操作次数。

动态规划状态定义

定义 f[i][p][q] 表示处理前 i 个元素后，使用了 p 次操作1和 q 次操作2时，前 i 个元素的最小和。

状态转移

对于第 i 个元素 nums[i-1]（假设数组从 0 开始），我们有以下选择：

1. 不进行任何操作：直接加上当前元素的值。
2. 进行操作1（如果 p > 0）：将当前元素除以 2 并向上取整，然后加上。
3. 进行操作2（如果 q > 0 且当前元素 >= k）：从当前元素中减去 k，然后加上。
4. 同时进行操作1和操作2（如果 p > 0 和 q > 0 且当前元素 >= k）：先进行操作2（减去 k），然后进行操作1（除以 2 并向上取整），或者反之。这里需要计算哪种顺序更优。

对于同时进行操作1和操作2的情况，需要计算两种顺序的结果：

• 先操作1后操作2：ceil((x + 1)/2) - k（如果 ceil((x + 1)/2) >= k）。
• 先操作2后操作1：ceil((x - k + 1)/2)。

我们需要选择这两种顺序中较小的值。

初始化

f[0][p][q] = 0 表示处理前 0 个元素的和为 0。

填充DP表

对于每个元素 nums[i-1]，遍历所有可能的 p 和 q，更新 f[i][p][q] 的值。

最终结果

最终结果是 f[n][op1][op2]，即处理完所有 n 个元素后，使用了 op1 次操作1和 op2 次操作2的最小和。

具体步骤

1. 初始化DP表：创建一个三维数组 f，大小为 (n+1) x (op1+1) x (op2+1)，初始值为 0。
2. 遍历每个元素：对于每个元素 nums[i-1]，从 i = 1 到 n：
- • 对于所有可能的 p（从 0 到 op1）和 q（从 0 到 op2）：
  - • 计算不进行操作、操作1、操作2以及同时操作1和操作2的最小值。
  - • 更新 f[i][p][q]。
3. 返回结果：f[n][op1][op2] 即为答案。

时间复杂度和空间复杂度

• 时间复杂度：我们需要遍历 n 个元素，对于每个元素，遍历 op1 + 1 和 op2 + 1 的所有组合。因此，时间复杂度为 O(n * op1 * op2)。
- • 由于 op1 和 op2 最多为 n，因此最坏情况下为 O(n^3)。
• 空间复杂度：DP表的大小为 (n+1) x (op1+1) x (op2+1)，因此空间复杂度为 O(n * op1 * op2)。
- • 同样，最坏情况下为 O(n^3)。

总结

通过动态规划，我们能够系统地考虑所有可能的操作组合，并找到使数组和最小的操作序列。该方法的时间复杂度和空间复杂度均为 O(n^3)，适用于题目给定的约束条件（n <= 100）。

Go完整代码如下：

package main

import (
    "fmt"
)

func minArraySum(nums []int, k, op1, op2 int)int {
    n := len(nums)
    f := make([][][]int, n+1)
    for i := range f {
        f[i] = make([][]int, op1+1)
        for j := range f[i] {
            f[i][j] = make([]int, op2+1)
        }
    }
    for i, x := range nums {
        var y int
        if (x+1)/2 >= k {
            y = (x+1)/2 - k
        } else {
            y = (x - k + 1) / 2
        }
        for p := 0; p <= op1; p++ {
            for q := 0; q <= op2; q++ {
                res := f[i][p][q] + x
                if p > 0 {
                    res = min(res, f[i][p-1][q]+(x+1)/2)
                }
                if q > 0 && x >= k {
                    res = min(res, f[i][p][q-1]+x-k)
                    if p > 0 {
                        res = min(res, f[i][p-1][q-1]+y)
                    }
                }
                f[i+1][p][q] = res
            }
        }
    }
    return f[n][op1][op2]
}

func main() {
    nums := []int{2, 8, 3, 19, 3}
    k := 3
    op1 := 1
    op2 := 1
    fmt.Println(minArraySum(nums, k, op1, op2))
}

Python完整代码如下：

# -*-coding:utf-8-*-

def minArraySum(nums, k, op1, op2):
    n = len(nums)
    # 初始化三维DP数组，维度为 (n+1) x (op1+1) x (op2+1)
    f = [[[float('inf')] * (op2+1) for _ in range(op1+1)] for _ in range(n+1)]
    f[0][0][0] = 0

    for i, x in enumerate(nums):
        # 计算 y，基于题意处理
        if (x + 1) // 2 >= k:
            y = (x + 1) // 2 - k
        else:
            y = (x - k + 1) // 2

        for p in range(op1+1):
            for q in range(op2+1):
                # 不操作当前元素
                res = f[i][p][q] + x

                # 操作1，除以2向上取整
                if p > 0:
                    res = min(res, f[i][p-1][q] + (x + 1) // 2)

                # 操作2，减去k（条件：x >= k）
                if q > 0 and x >= k:
                    res = min(res, f[i][p][q-1] + x - k)

                    # 操作1和操作2都做
                    if p > 0:
                        res = min(res, f[i][p-1][q-1] + y)

                f[i+1][p][q] = res

    return f[n][op1][op2]


if __name__ == '__main__':
    nums = [2, 8, 3, 19, 3]
    k = 3
    op1 = 1
    op2 = 1
    print(minArraySum(nums, k, op1, op2))