只要
C(m)如此神奇,您就不能使用任何更好的技术来直接找到您的解决方案,因此您确实需要以
a*b递减的顺序遍历所有内容,这就是我要做的:
用所有对初始化一个max-heap,
(a, b)使
a = b。这意味着堆包含
(0, 0), (1, 1), ... , (1.000.000,1.000.000)。堆应该基于该
a * b值。
现在不断:
(a, b)
从堆中获取最大对。- 验证是否
(a, b)
满意C(a * b)
。如果是这样,您就完成了。 - 否则,添加
(a, b-1)
到堆中(已提供b > 0
,否则什么也不做)。
这是一个非常简单的
O(n log n)时间和
O(n)空间算法,只要您能够快速找到答案(几次迭代)即可。这当然取决于
C。
如果遇到空间问题,您当然可以通过将问题分成多个子问题来轻松地降低空间复杂度,例如2:
- 只添加
(500.000, 500.000), (500.001, 500.001), ... , (1.000.000, 1.000.000)
到堆中,找到最合适的一对(a, b)
。 - 对进行相同操作
(0, 0), (1, 1), ... (499.999, 499.999)
。 - 采取两种解决方案中最好的一种。



