3091. 执行操作使数据元素之和大于等于 K

题目描述

给你一个正整数 k 。最初，你有一个数组 nums = [1] 。

你可以对数组执行以下任意操作任意次数（可能为零）：

选择数组中的任何一个元素，然后将它的值增加 1 。
复制数组中的任何一个元素，然后将它附加到数组的末尾。

返回使得最终数组元素之和大于或等于 k 所需的最少操作次数。

示例 1：

输入：k = 11

输出：5

解释：

可以对数组 nums = [1] 执行以下操作：

将元素的值增加 1 三次。结果数组为 nums = [4] 。
复制元素两次。结果数组为 nums = [4,4,4] 。

最终数组的和为 4 + 4 + 4 = 12 ，大于等于 k = 11 。
执行的总操作次数为 3 + 2 = 5 。

示例 2：

输入：k = 1

输出：0

解释：

原始数组的和已经大于等于 1 ，因此不需要执行操作。

提示：

1 <= k <= 10⁵

解法

方法一：枚举

我们应该将复制的操作（即操作 $2$）放后面，这样可以减少操作次数。

因此，我们在 $[0, k]$ 的范围内枚举操作 $1$ 的次数 $a$，那么操作 $2$ 的次数 $b = \left\lceil \frac{k}{a+1} \right\rceil - 1$。取最小的 $a+b$ 即可。

时间复杂度 $O(k)$，其中 $k$ 为输入的正整数 $k$。空间复杂度 $O(1)$。

Python3JavaC++GoTypeScript

class Solution:
    def minOperations(self, k: int) -> int:
        ans = k
        for a in range(k):
            x = a + 1
            b = (k + x - 1) // x - 1
            ans = min(ans, a + b)
        return ans

class Solution {
    public int minOperations(int k) {
        int ans = k;
        for (int a = 0; a < k; ++a) {
            int x = a + 1;
            int b = (k + x - 1) / x - 1;
            ans = Math.min(ans, a + b);
        }
        return ans;
    }
}

class Solution {
public:
    int minOperations(int k) {
        int ans = k;
        for (int a = 0; a < k; ++a) {
            int x = a + 1;
            int b = (k + x - 1) / x - 1;
            ans = min(ans, a + b);
        }
        return ans;
    }
};

func minOperations(k int) int {
    ans := k
    for a := 0; a < k; a++ {
        x := a + 1
        b := (k+x-1)/x - 1
        ans = min(ans, a+b)
    }
    return ans
}

function minOperations(k: number): number {
    let ans = k;
    for (let a = 0; a < k; ++a) {
        const x = a + 1;
        const b = Math.ceil(k / x) - 1;
        ans = Math.min(ans, a + b);
    }
    return ans;
}

3091. 执行操作使数据元素之和大于等于 K

题目描述

解法

方法一：枚举

评论