Leetcode 3091. Apply Operations to Make Sum of Array Greater Than or Equal to k

2024-03-24 18:20

本文主要是介绍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的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/842388

相关文章

Kotlin 作用域函数apply、let、run、with、also使用指南

《Kotlin作用域函数apply、let、run、with、also使用指南》在Kotlin开发中,作用域函数(ScopeFunctions)是一组能让代码更简洁、更函数式的高阶函数,本文将... 目录一、引言:为什么需要作用域函数?二、作用域函China编程数详解1. apply:对象配置的 “流式构建器”最

JavaScript Array.from及其相关用法详解(示例演示)

《JavaScriptArray.from及其相关用法详解(示例演示)》Array.from方法是ES6引入的一个静态方法,用于从类数组对象或可迭代对象创建一个新的数组实例,本文将详细介绍Array... 目录一、Array.from 方法概述1. 方法介绍2. 示例演示二、结合实际场景的使用1. 初始化二

Golan中 new() 、 make() 和简短声明符的区别和使用

《Golan中new()、make()和简短声明符的区别和使用》Go语言中的new()、make()和简短声明符的区别和使用,new()用于分配内存并返回指针,make()用于初始化切片、映射... 详细介绍golang的new() 、 make() 和简短声明符的区别和使用。文章目录 `new()`

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

最大流=最小割=最小点权覆盖集=sum-最大点权独立集

二分图最小点覆盖和最大独立集都可以转化为最大匹配求解。 在这个基础上,把每个点赋予一个非负的权值,这两个问题就转化为:二分图最小点权覆盖和二分图最大点权独立集。   二分图最小点权覆盖     从x或者y集合中选取一些点,使这些点覆盖所有的边,并且选出来的点的权值尽可能小。 建模:     原二分图中的边(u,v)替换为容量为INF的有向边(u,v),设立源点s和汇点t

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return