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

举报
福大大架构师每日一题 发表于 2025/06/16 06:33:24 2025/06/16
【摘要】 2025-06-16:最小数组和。用go语言,你有一个整数数组 nums 和三个整数 k、op1、op2。你可以对数组进行以下两种操作:操作1:选择一个元素,将该元素除以2后向上取整。最多能执行 op1 次,每个元素最多执行一次此操作。操作2:选择一个元素,仅当它的值不少于 k 时,从该元素中减去 k。最多能执行 op2 次,每个元素最多执行一次此操作。同一个元素可以同时执行这两种操作,但每...

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 > 0q > 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],遍历所有可能的 pq,更新 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 = 1n
    • 对于所有可能的 p(从 0 到 op1)和 q(从 0 到 op2):
      • 计算不进行操作、操作1、操作2以及同时操作1和操作2的最小值。
      • 更新 f[i][p][q]
  3. 返回结果f[n][op1][op2] 即为答案。

时间复杂度和空间复杂度

  • 时间复杂度:我们需要遍历 n 个元素,对于每个元素,遍历 op1 + 1op2 + 1 的所有组合。因此,时间复杂度为 O(n * op1 * op2)
    • 由于 op1op2 最多为 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))

在这里插入图片描述

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。