难度: Medium
给你一个正整数 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运行时间: 19 ms
内存: 16.1 MB
class Solution:
def minOperations(self, k: int) -> int:
# 11 =5*2+1 +>4+1+1
# 15 =3*5 2+5 4+3
# 15 = 4*4 3 +4
# 贪心
# 先构造一个最大值， 然后将其复制 n 次
# 复制的代价跟+1 一样 ， 也就是 假设 nums[i]=6 k=7 此时 i+1 与 6,6 是相同的
# 我们主要以复制为主？
# 模拟+二分试试
ans=k-1
if ans==0:return ans
n,d=k,1
while 1:
while d*n>=k:
n-=1
d+=1
if (n-1)+(d-1)>ans:
break
ans=(n-1)+(d-1)
return ans
这个题解尝试通过增加和复制数组中的元素来达到和大于等于k的目的。题解中的思路似乎是试图找到一个使总成本最小化的策略。初始设置操作最大次数为k-1（一种极端情况下的估计，即每次只增加1直到达到k）。然后通过一个循环，尝试找到一个较小的操作数。在循环中，维护两个变量n和d，其中n代表当前的元素值，d代表复制操作的次数。循环的目标是在增加和复制的代价内找到最少的总操作次数。如果通过尝试所有可能的n和d组合后，发现更小的操作次数，则更新答案。这种方法的有效性依赖于对问题的理解和正确的实现。
时间复杂度: O(k^2)
空间复杂度: O(1)
class Solution:
def minOperations(self, k: int) -> int:
ans = k - 1 # 初始化操作次数为k-1，最坏情况
if ans == 0: return ans # 如果k为1，无需操作
n, d = k, 1 # n为当前元素值，d为复制次数
while True:
while d * n >= k: # 当当前总和大于等于k时
n -= 1 # 减小元素值尝试找到更优解
d += 1 # 增加复制次数
if (n - 1) + (d - 1) > ans: # 如果当前操作次数超过已找到的最小值
break # 终止循环
ans = (n - 1) + (d - 1) # 更新最小操作次数
return ans # 返回最小操作次数
在题解中，将操作次数初始化为k-1是基于极端情况的考虑，即最初数组仅包含一个元素1，而要使其总和达到k，至少需要将这个元素从1增加到k，这需要k-1次增加操作。这种情况假设我们只使用增加操作而不使用复制操作，因此这是一种保守的估计，用于确保不会漏掉可能需要的最大操作次数。
在循环中将n的初始值设为k是出于优化操作的考虑。设n为k意味着我们从最大可能需要的单个元素值开始尝试，然后逐渐减小n的值寻找可能的更优解。这样做可以快速检查较大的n值是否能够在较少的操作次数下达到目标k，从而优化整体操作次数。
这个循环终止条件确保了一旦当前尝试的操作次数`(n - 1) + (d - 1)`超过了已知的最小操作次数`ans`，就停止进一步尝试。这是因为如果当前的操作次数已经超过了已知的最小值，继续增加复制次数或减少n的值只会增加操作次数。因此，该条件确保了一旦找到一个操作次数较小的解，就不会错过它，并且会在找到更优解之前停止尝试不必要或者无效的情况。