本文主要是介绍Leetcode 3091. Apply Operations to Make Sum of Array Greater Than or Equal to k,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
- Leetcode 3091. Apply Operations to Make Sum of Array Greater Than or Equal to k
- 1. 解题思路
- 2. 代码实现
- 题目链接:3091. Apply Operations to Make Sum of Array Greater Than or Equal to k
1. 解题思路
这一题的话本质上算是一个数学题,具体就是:
- 已知: ( 1 + x ) ( 1 + y ) ≥ k (1+x)(1+y) \geq k (1+x)(1+y)≥k,求 x + y x+y x+y的最小值。
显然有基本不等式:
[ ( x + 1 ) + ( y + 1 ) 2 ] 2 ≥ ( x + 1 ) ( y + 1 ) ≥ k [\frac{(x+1)+(y+1)}{2}]^2 \geq (x+1)(y+1) \geq k [2(x+1)+(y+1)]2≥(x+1)(y+1)≥k
当 x = y x=y x=y时取到最小值,因此,我们只需要令 x , y x, y x,y尽可能相同即可,因此,我们就可以直接求得 x , y x, y x,y的值了。
2. 代码实现
给出python代码实现如下:
class Solution:def minOperations(self, k: int) -> int:t = math.ceil(math.sqrt(k))p = math.ceil(k / t)return t-1 + p-1
提交代码评测得到:耗时43ms,占用内存16.6MB。
这篇关于Leetcode 3091. Apply Operations to Make Sum of Array Greater Than or Equal to k的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!