Skip to content

Latest commit

 

History

History
331 lines (282 loc) · 11.5 KB

README_EN.md

File metadata and controls

331 lines (282 loc) · 11.5 KB
comments difficulty edit_url rating source tags
true
Medium
2040
Weekly Contest 425 Q3
Array
Dynamic Programming

3366. Minimum Array Sum

中文文档

Description

You are given an integer array nums and three integers k, op1, and op2.

You can perform the following operations on nums:

  • Operation 1: Choose an index i and divide nums[i] by 2, rounding up to the nearest whole number. You can perform this operation at most op1 times, and not more than once per index.
  • Operation 2: Choose an index i and subtract k from nums[i], but only if nums[i] is greater than or equal to k. You can perform this operation at most op2 times, and not more than once per index.

Note: Both operations can be applied to the same index, but at most once each.

Return the minimum possible sum of all elements in nums after performing any number of operations.

 

Example 1:

Input: nums = [2,8,3,19,3], k = 3, op1 = 1, op2 = 1

Output: 23

Explanation:

  • Apply Operation 2 to nums[1] = 8, making nums[1] = 5.
  • Apply Operation 1 to nums[3] = 19, making nums[3] = 10.
  • The resulting array becomes [2, 5, 3, 10, 3], which has the minimum possible sum of 23 after applying the operations.

Example 2:

Input: nums = [2,4,3], k = 3, op1 = 2, op2 = 1

Output: 3

Explanation:

  • Apply Operation 1 to nums[0] = 2, making nums[0] = 1.
  • Apply Operation 1 to nums[1] = 4, making nums[1] = 2.
  • Apply Operation 2 to nums[2] = 3, making nums[2] = 0.
  • The resulting array becomes [1, 2, 0], which has the minimum possible sum of 3 after applying the operations.

 

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 105
  • 0 <= k <= 105
  • 0 <= op1, op2 <= nums.length

Solutions

Solution 1: Dynamic Programming

For convenience, we denote the given $k$ as $d$.

Next, we define $f[i][j][k]$ to represent the minimum sum of the first $i$ numbers using $j$ operations of type 1 and $k$ operations of type 2. Initially, $f[0][0][0] = 0$, and the rest $f[i][j][k] = +\infty$.

Consider how to transition the state for $f[i][j][k]$. We can enumerate the $i$-th number $x$ and then consider the impact of $x$ on $f[i][j][k]$:

  • If $x$ does not use operation 1 or operation 2, then $f[i][j][k] = f[i-1][j][k] + x$;
  • If $j \gt 0$, then we can use operation 1. In this case, $f[i][j][k] = \min(f[i][j][k], f[i-1][j-1][k] + \lceil \frac{x+1}{2} \rceil)$;
  • If $k \gt 0$ and $x \geq d$, then we can use operation 2. In this case, $f[i][j][k] = \min(f[i][j][k], f[i-1][j][k-1] + (x - d))$;
  • If $j \gt 0$ and $k \gt 0$, then we can use both operation 1 and operation 2. If we use operation 1 first, then $x$ becomes $\lceil \frac{x+1}{2} \rceil$. If $x \geq d$, then we can use operation 2. In this case, $f[i][j][k] = \min(f[i][j][k], f[i-1][j-1][k-1] + \lceil \frac{x+1}{2} \rceil - d)$. If we use operation 2 first, then $x$ becomes $x - d$. If $x \geq d$, then we can use operation 1. In this case, $f[i][j][k] = \min(f[i][j][k], f[i-1][j-1][k-1] + \lceil \frac{x-d+1}{2} \rceil)$.

The final answer is $\min_{j=0}^{op1} \min_{k=0}^{op2} f[n][j][k]$. If it is $+\infty$, then output $-1$.

The time complexity is $O(n \times \textit{op1} \times \textit{op2})$, and the space complexity is $O(n \times \textit{op1} \times \textit{op2})$. Here, $n$ is the length of the array $\textit{nums}$.

Python3

class Solution:
    def minArraySum(self, nums: List[int], d: int, op1: int, op2: int) -> int:
        n = len(nums)
        f = [[[inf] * (op2 + 1) for _ in range(op1 + 1)] for _ in range(n + 1)]
        f[0][0][0] = 0
        for i, x in enumerate(nums, 1):
            for j in range(op1 + 1):
                for k in range(op2 + 1):
                    f[i][j][k] = f[i - 1][j][k] + x
                    if j > 0:
                        f[i][j][k] = min(f[i][j][k], f[i - 1][j - 1][k] + (x + 1) // 2)
                    if k > 0 and x >= d:
                        f[i][j][k] = min(f[i][j][k], f[i - 1][j][k - 1] + (x - d))
                    if j > 0 and k > 0:
                        y = (x + 1) // 2
                        if y >= d:
                            f[i][j][k] = min(f[i][j][k], f[i - 1][j - 1][k - 1] + y - d)
                        if x >= d:
                            f[i][j][k] = min(
                                f[i][j][k], f[i - 1][j - 1][k - 1] + (x - d + 1) // 2
                            )
        ans = inf
        for j in range(op1 + 1):
            for k in range(op2 + 1):
                ans = min(ans, f[n][j][k])
        return ans

Java

class Solution {
    public int minArraySum(int[] nums, int d, int op1, int op2) {
        int n = nums.length;
        int[][][] f = new int[n + 1][op1 + 1][op2 + 1];
        final int inf = 1 << 29;
        for (var g : f) {
            for (var h : g) {
                Arrays.fill(h, inf);
            }
        }
        f[0][0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            int x = nums[i - 1];
            for (int j = 0; j <= op1; ++j) {
                for (int k = 0; k <= op2; ++k) {
                    f[i][j][k] = f[i - 1][j][k] + x;
                    if (j > 0) {
                        f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j - 1][k] + (x + 1) / 2);
                    }
                    if (k > 0 && x >= d) {
                        f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j][k - 1] + (x - d));
                    }
                    if (j > 0 && k > 0) {
                        int y = (x + 1) / 2;
                        if (y >= d) {
                            f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j - 1][k - 1] + (y - d));
                        }
                        if (x >= d) {
                            f[i][j][k]
                                = Math.min(f[i][j][k], f[i - 1][j - 1][k - 1] + (x - d + 1) / 2);
                        }
                    }
                }
            }
        }
        int ans = inf;
        for (int j = 0; j <= op1; ++j) {
            for (int k = 0; k <= op2; ++k) {
                ans = Math.min(ans, f[n][j][k]);
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int minArraySum(vector<int>& nums, int d, int op1, int op2) {
        int n = nums.size();
        int f[n + 1][op1 + 1][op2 + 1];
        memset(f, 0x3f, sizeof f);
        f[0][0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            int x = nums[i - 1];
            for (int j = 0; j <= op1; ++j) {
                for (int k = 0; k <= op2; ++k) {
                    f[i][j][k] = f[i - 1][j][k] + x;
                    if (j > 0) {
                        f[i][j][k] = min(f[i][j][k], f[i - 1][j - 1][k] + (x + 1) / 2);
                    }
                    if (k > 0 && x >= d) {
                        f[i][j][k] = min(f[i][j][k], f[i - 1][j][k - 1] + (x - d));
                    }
                    if (j > 0 && k > 0) {
                        int y = (x + 1) / 2;
                        if (y >= d) {
                            f[i][j][k] = min(f[i][j][k], f[i - 1][j - 1][k - 1] + (y - d));
                        }
                        if (x >= d) {
                            f[i][j][k] = min(f[i][j][k], f[i - 1][j - 1][k - 1] + (x - d + 1) / 2);
                        }
                    }
                }
            }
        }
        int ans = INT_MAX;
        for (int j = 0; j <= op1; ++j) {
            for (int k = 0; k <= op2; ++k) {
                ans = min(ans, f[n][j][k]);
            }
        }
        return ans;
    }
};

Go

func minArraySum(nums []int, d int, op1 int, op2 int) int {
	n := len(nums)
	const inf = int(1e9)
	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 k := range f[i][j] {
				f[i][j][k] = inf
			}
		}
	}
	f[0][0][0] = 0
	for i := 1; i <= n; i++ {
		x := nums[i-1]
		for j := 0; j <= op1; j++ {
			for k := 0; k <= op2; k++ {
				f[i][j][k] = f[i-1][j][k] + x
				if j > 0 {
					f[i][j][k] = min(f[i][j][k], f[i-1][j-1][k]+(x+1)/2)
				}
				if k > 0 && x >= d {
					f[i][j][k] = min(f[i][j][k], f[i-1][j][k-1]+(x-d))
				}
				if j > 0 && k > 0 {
					y := (x + 1) / 2
					if y >= d {
						f[i][j][k] = min(f[i][j][k], f[i-1][j-1][k-1]+(y-d))
					}
					if x >= d {
						f[i][j][k] = min(f[i][j][k], f[i-1][j-1][k-1]+(x-d+1)/2)
					}
				}
			}
		}
	}
	ans := inf
	for j := 0; j <= op1; j++ {
		for k := 0; k <= op2; k++ {
			ans = min(ans, f[n][j][k])
		}
	}
	return ans
}

TypeScript

function minArraySum(nums: number[], d: number, op1: number, op2: number): number {
    const n = nums.length;
    const inf = Number.MAX_SAFE_INTEGER;

    const f: number[][][] = Array.from({ length: n + 1 }, () =>
        Array.from({ length: op1 + 1 }, () => Array(op2 + 1).fill(inf)),
    );
    f[0][0][0] = 0;

    for (let i = 1; i <= n; i++) {
        const x = nums[i - 1];
        for (let j = 0; j <= op1; j++) {
            for (let k = 0; k <= op2; k++) {
                f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j][k] + x);
                if (j > 0) {
                    f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j - 1][k] + Math.floor((x + 1) / 2));
                }
                if (k > 0 && x >= d) {
                    f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j][k - 1] + (x - d));
                }
                if (j > 0 && k > 0) {
                    const y = Math.floor((x + 1) / 2);
                    if (y >= d) {
                        f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j - 1][k - 1] + (y - d));
                    }
                    if (x >= d) {
                        f[i][j][k] = Math.min(
                            f[i][j][k],
                            f[i - 1][j - 1][k - 1] + Math.floor((x - d + 1) / 2),
                        );
                    }
                }
            }
        }
    }

    let ans = inf;
    for (let j = 0; j <= op1; j++) {
        for (let l = 0; l <= op2; l++) {
            ans = Math.min(ans, f[n][j][l]);
        }
    }
    return ans;
}