两个执行程序共享作业的算法

Question

我在测试一些网站时遇到了以下问题：

John和Mary创立了J&M出版社，并购买了两台旧打印机 来装备它。现在他们有了他们的第一份商业交易——打印一个 文档由 N 页组成。打印机似乎在 不同的速度。一个在 X 秒内生成一个页面，另一个在 Y 秒。所以现在公司创始人对他们最短的时间感到好奇。 可以用两台打印机打印整个文档。

（取自此处 http://codeabbey.com/index/task_view/two-printers）

我认为这是贪婪算法的问题，但被告知 N 可能高达 10 亿，所以也许有一些更简单的解决方案，我看不到。我能否以某种方式将它们按 X 和 Y 的比例划分

Answer 1

这似乎是一个数学问题，而不是算法问题。作业分配将是YN/(X+Y)页到X，XN/(X+Y)页到Y。总时间将是XYN/(X+Y)哪个是最佳的（请注意，它相当于N/(1/X + 1/Y)。由于YN/(X+Y)可能不是整数，因此您可以只计算几个值（如果X向上舍入，Y向下舍入，反之亦然），然后取最小值。或者正如您所说，您可以将两者四舍五入，并将任何剩余的作业分配给更快的机器。

Answer 2

for i in range(int(input())):
    x,y,n = list(map(float, input().split()))
    x_1 = int(y*n / (x+y))
    y_1 = int(x*n/ (x+y))
    n = n - (x_1 + y_1)
    x_ans = int(max( (x_1 + n)* x, y_1 * y))
    y_ans = int(max( x_1 * x, (y_1 + n) * y))
    print(min(x_ans,y_ans),end=' ')