algorithm - 如何找到解决所有 N 问题所需的最短时间？

Question

我试图解决这个问题，但即使在几个小时后我也无法解决完全理解问题。我什至无法上来使用任何蛮力技术。这就是问题:

There are N members and N problems and each member must exactly solve 1 problem.Only one member of the from the team is allowed to read the problem statements before anyone start to solve.

Note that not everyone have read the problems at first. So, to solve problems a member needs to know the statements from some teammate who already knows them. After knowing problems once, a member is eligible to explain them to other teammates ( one teammate at a time ). You can assume that the explaining ( 1 or N problems ) will always take D minutes. During explaining, none of the two involved members will be able to do anything else.

Problems are of different difficulty levels. You can assume that it will take Ti minutes to solve the ith problem, regardless of which member solves it.

Given a team's data, what is the minimum possible time in which they can solve all problems?

输入

N  D
2 100

T=[1 2]

Output

102

Member 1 is allowed to know problems before start time. He starts explaing problems to member 2 when contest starts. Explaining ends at the 100th minute. Then both of them immidiately starts solving problems parallely. Member 1 solved 1st problem at the 101th minute and member 2 solved 2nd problem at the 102th minute.

解码和处理此类问题的最佳方法是什么？

Answer 1

这让我想起了 Huffman coding .

我不确定以下方法是否是最优的，但它可能会在实践中给出一个很好的答案。

1. 选择最简单的两个问题 T0 和 T1，并将它们替换为一个由时间 D+max(T0,T1) 组成的问题。
2. 重复直到剩下一个问题

如果将问题存储在二进制堆中，则可以在 O(logN) 中找到两个最简单的问题，因此总体而言这是 O(NlogN)。

例子

假设我们有 1,3,4,6 并且 D=2。

我们首先结合 1 和 3 使 2+max(1,3)=5。新列表是 4,5,6

然后我们将 4 和 5 结合起来使 2+max(4,5)=7。新列表是 6,7。

然后我们将 6 和 7 结合起来使 2+max(6,7)=9。

这表示以下过程。

t=0 A shares with B
t=2 A starts problem 6, B shares with C
t=4 B starts problem 4, C shares with D
t=6 C starts problem 3, D starts problem 1
t=7 D finishes
t=8 A finishes, B finishes
t=9 C finishes