README.md

comments	difficulty	edit_url	rating	source	tags
true	中等	https://github.com/doocs/leetcode/edit/main/solution/3000-3099/3091.Apply%20Operations%20to%20Make%20Sum%20of%20Array%20Greater%20Than%20or%20Equal%20to%20k/README.md	1521	第 390 场周赛 Q2	贪心 数学 枚举

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

English Version

题目描述

给你一个正整数 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 <= 105

解法

方法一：枚举

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

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

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

Python3

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

Java

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;
    }
}

C++

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;
    }
};

Go

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
}

TypeScript

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;
}