- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
给定一个正数数组。我想将数组拆分为 2 个不同的子集,以使它们的 gcd(最大公约数)之和最大。
示例数组:{6,7,6,7}
。
答案:需要的两个子集是:{6,6}
和{7,7}
;它们各自的 gcd(s) 是 6 和 7,它们的 sum = 6+7=13
;这是可能的最大 gcd 总和。
Gcd:{8,12}
的 Gcd 是 {4}
,因为 4 是 8 和 12 的最大数。
注意:gcd(X)=X
如果子集只包含一个元素。
我的方法:通过暴力破解,找到数组所有可能的子序列,然后找到最大和,但如果输入大小大于 30 个数字,这将不起作用。我正在寻找更有效的方法。
Extra(s): 任何输入数字的最大大小为 10^9 ,时间限制:-1s 似乎不错,输入的大小可能与 10^5 一样大
最佳答案
我觉得这其实是一个容易的问题。
首先,让我们忽略值出现不止一次的可能性。显然,最好将一个值的所有拷贝放在同一个集合中,因为将其中一些拷贝移到别处只会损害 GCD(编辑:,除非只有一个不同的值)。所以我们假设所有元素都是不同的。此外,令 M 为任何元素的最大值。
这样想:有一个简单的解决方案,将最高元素放在一侧,将所有其余元素放在另一侧。 “其余所有”- GCD 可能为 1(当然可能更高),因此此解决方案为您提供 M+1。
具有多个不同元素的任何输入子集的 GCD 都不能高于 M/2(因为这样的一个除数必须乘以另一个至少为 2 的除数才能得到原始值,不高于 M)。所以编辑:最佳解决方案不能由两个集合组成,每个集合都有多个不同的元素。它必须是一个元素与所有其他元素。
现在考虑两个最高的元素,对于某些 d 具有值 M 和 M-d。如果我们不选择它们中的任何一个作为单例,则它们都在大组侧,这意味着该组的 GCD 最多为 d(因为如果 g|M 和 g|M-d 则 g|d);并且单例的贡献不会超过 M-d-1。所以总分最多为 M-1——也就是说,小于我们在选择最高值时得到的分数。 因此,输入中的最高值或第二高(不同)值必须在其自己的集合中。
因此,您必须执行以下操作:
关于c++ - 最大化二分法的 GCD(最大公约数)之和?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56503879/
给定一个包含 n 个非负整数的数组:A1、A2、...、AN。如何找到一对整数 Au, Av (1 ≤ u ans) { ans=arr[i] & arr[j
有人知道这段代码的正确解决方案吗? BOOL maximized = [myWindow isMaximized]; 最佳答案 也许看看 isZoomed 关于cocoa - NSWindow 最大化
当前有一个 MySQL 数据库,但遇到 MySQL 以 600% CPU 使用率运行的问题。 规范: 2.3 GHz Intel Xeon® E5-2686 v4 (Broadwell) 处理器或 2
我已将 Skype 配置为在 Windows 启动时最小化启动。 现在我需要通过全屏应用程序按钮中的一个按钮将 Skype 置于最前面。我有这段代码: For Each p As Proces
我已经有一段时间没有做任何生疏的程序了。我正在研究代码以最大化和最小化其他应用程序。所以我找到了一些基本的东西,这就是我所拥有的,对原来的东西稍作修改。它希望我生成一些我所做的 FindWindow
我有一个 Windows CE 应用程序,它记录移动设备的击键。有一个用于初始化录制功能的按钮,它通过调用强制主窗口最小化: ShowWindow (hWnd, SW_MINIMIZE); 在最小化窗
我想显示一个占据尽可能多屏幕空间的对话框。 所以,这是一个示例: AlertDialog dialog = new AlertDialog.Builder(ctx)......create(); Wi
对Wndows用户来说,最小化/最大化/关闭按钮放在系统窗口的右上角是肯定的。而大多数朋友都是成为Wndows用户之后才成为Ubuntu用户的,因此Ubuntu程序窗口中将这些按键放在左上角使用起来
1.Ctrl+Alt+T调出终端 2.首先安装gconf-editor: sudo apt-get install gconf-editor 会提示叫你安装 gconf-editor 安装完成
Width最大化窗口时,屏幕的属性似乎没有更新到完全最大化的宽度。如果我调整它的大小,一切正常,但在最大化时就不行。 我的代码如下: private void Window_SizeChanged(o
我正在这个 fiddle 中使用指令和 = 绑定(bind)。我收到以下错误: Uncaught Error: 10 $digest() iterations reached. Aborting! W
是否有任何快捷方式可以最大化您在 Eclipse 中使用的选项卡?假设我正在处理代码的一部分,并且我想最大化选项卡而不是使用鼠标双击它,有人知道一种方法吗? 最佳答案 CtrlM 将最大化/恢复编辑器
在 Glassdoor 评论中遇到这个问题,觉得很有趣。 Given an integer consisting of 4 digits, we need to maximize it in 24 h
在 VB6 中,我创建了一个带有一些文本框、列表框和命令按钮的表单。我使用类似 的方法设置所有这些控件的 X-Y 位置 control2.Top = form.Height * 0.50 'set
到处都有人告诉我使用这个: frame.setExtendedState(JFrame.MAXIMIZED_BOTH); 但问题是我的 JMenuBar 时断时续地消失(发生在我身上的奇怪错误),并且
我有一个 JDesktopPane 和一个 JInternalFrame。我希望 JInternalFrame 在创建后自动最大化。如何对“最大化窗口”事件进行硬编码? 最佳答案 使用JInterna
这个问题已经有答案了: JFrame doesn't take the actual screen size (2 个回答) 已关闭 3 年前。 我想最大化我的 JFrame,就像按下“关闭”旁边的按
我正在使用 vim 和 python 编程,并使用 tpope's vim-dispatch通过运行当前文件 :Dispatch python main.py 程序的打印输出被定向到quickfix窗
假设我们有一个名为 total 的 NSDecimal 常量,它包含 3.33333333 除以 10/3 的值。 10 和 3 都是NSDecimalNumber。我们希望 Swift 中的 NSD
有谁知道如何在发生特定操作后最大化 JFrame?我将在下面发布我的代码,我是一个不评论我的代码的恶魔(我会在某个时候这样做)但它应该是相当 self 解释的。我试图做的是在从菜单中选择选项后使框架最
我是一名优秀的程序员,十分优秀!