如何找到解决所有 N 问题所需的最短时间？
How to find the minimum time required to solve all N problems?
我试图解决这个问题，但即使在下班后我也无法解决
完全理解问题。我什至无法上来
使用任何蛮力 techniques.This 是问题：
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.
解决此类问题的最佳方法是什么？
团队的每一位成员（阅读问题的人除外）
必须听到的问题。也就是说，有问题必须讲N - 1次。
对于 N = 2，这可以在 D 分钟内完成，
在 2D 分钟后 2 < N <= 4，
4 < N <= 8 3D 分钟等
如果N不是2的精确次方那么一定有人说完了
问题至少比其他问题早 D 分钟。
提前完成的人可以继续工作
最难的题，把容易的题留给后来完成的人。
如果有些问题需要时间 Ti > D 并且 N 既不准确
2 的幂也不小于 2 的精确幂，你可能想要
有人比 D 分钟前 多 不再讲问题
最后一道题讲完
如果某些问题需要时间 Ti > 2D 那么您可能需要考虑
让一些人停止讲述问题并开始真正地工作
即使 N 是 2.
的精确幂，也会更快遇到难题
由于解决一个问题是每个成员的关键路径，
但讲述是在多个成员的关键路径中，
任何人在完成之前解决问题都是没有意义的
讲述他们将要做的所有问题。
每 D 分钟后知道问题的人数
随着提出问题的人数增加。
提出问题的人数随着提出问题的人数的增加而增加
正在讲题（即刚学会的人数
问题）减去当时开始处理问题的人数。
一个好的 "brute force" 方法可能是对问题进行排序
按难度；然后找出时间直到最后一个人听到
如果在此之前没有人开始研究这些问题；
找出最后一个人完成的时间；
然后尝试提前 D 分钟或 2D 分钟开始做题，
或 3D 分钟等，但永远不要开始更短 - 运行
在更长的运行之前出现问题。
这让我想起了 Huffman coding。
我不确定下面的方法是否最优，但在实践中它可能会给出一个很好的答案。
- 选择最简单的两个问题 T0 和 T1，并将它们替换为由时间 D+max(T0,T1) 组成的单个问题。
- 重复直到剩下一个问题
如果将问题存储在二进制堆中，则可以在 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
问题陈述的解释部分有些含糊不清。根据语句的解释方式，可能有以下解决方案：
如果假设你可以在D分钟内解释N道题，那么解释一道题需要N/D分钟。我们称其为 Te，因为 "time to explain"。而解决问题 i 的时间是 Ti，我们知道这等于 i 分钟。
所以在比赛开始时，成员 1（知道所有问题）向成员 2 解释问题 N。这需要 Te 分钟。然后，成员 2 开始解决问题 N（需要 N 分钟才能解决），成员 1 开始向成员 3 解释问题 N-1。这一直持续到成员 1 向成员 N 解释问题 2。此时，成员 N 开始正在处理问题 2，成员 1 开始处理问题 1。
假设有 4 个问题，4 个团队成员，D=8。所以Te=2.
Time Description
0 Member 1 begins explaining Problem 4 to Member 2
2 Member 2 begins working on Problem 4
Member 1 begins explaining Problem 3 to Member 3
4 Member 3 begins working on Problem 3
Member 1 begins explaining Problem 2 to Member 4
6 Member 2 completes problem 4
Member 4 begins working on Problem 2
Member 1 begins working on Problem 1
7 Member 3 completes Problem 3
Member 1 completes Problem 1
8 Member 4 completes Problem 2
无论 D 或 N 的值如何，这似乎都是最佳解决方案：安排它以便尽可能早地开始解决花费时间最长的问题。
我怀疑问题陈述是用其他语言给出的问题的英文翻译，或者可能是对最初用英文编写并翻译成其他语言的内容的重新翻译。因为如果那是最初的问题陈述，那么应该禁止编写它的人再次编写问题。
完成任何一项任务所需的时间长度似乎具有 C * D + T, where C is a positive integer less than N 的形式，并且必须考虑所有 N-1 的提前期。假设我们犯了一个错误，最佳解决方案实际上应该有一个任务加上更长的交付时间——所以一些 C * D + Tj < C * D + Ti, where Ti < Tj，这是不可能的。
因此，对对的总和进行一次迭代（假设输入已排序）：
solution = maximum (T2 + (n-1) * D, T3 + (n-2) * D...D + Tn)
我试图解决这个问题，但即使在下班后我也无法解决 完全理解问题。我什至无法上来 使用任何蛮力 techniques.This 是问题：
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.
解决此类问题的最佳方法是什么？
团队的每一位成员（阅读问题的人除外）
必须听到的问题。也就是说，有问题必须讲N - 1次。
对于 N = 2，这可以在 D 分钟内完成，
在 2D 分钟后 2 < N <= 4，
4 < N <= 8 3D 分钟等
如果N不是2的精确次方那么一定有人说完了
问题至少比其他问题早 D 分钟。
提前完成的人可以继续工作
最难的题，把容易的题留给后来完成的人。
如果有些问题需要时间 Ti > D 并且 N 既不准确
2 的幂也不小于 2 的精确幂，你可能想要
有人比 D 分钟前 多 不再讲问题
最后一道题讲完
如果某些问题需要时间 Ti > 2D 那么您可能需要考虑
让一些人停止讲述问题并开始真正地工作
即使 N 是 2.
由于解决一个问题是每个成员的关键路径，
但讲述是在多个成员的关键路径中，
任何人在完成之前解决问题都是没有意义的
讲述他们将要做的所有问题。
每 D 分钟后知道问题的人数
随着提出问题的人数增加。
提出问题的人数随着提出问题的人数的增加而增加
正在讲题（即刚学会的人数
问题）减去当时开始处理问题的人数。
一个好的 "brute force" 方法可能是对问题进行排序
按难度；然后找出时间直到最后一个人听到
如果在此之前没有人开始研究这些问题；
找出最后一个人完成的时间；
然后尝试提前 D 分钟或 2D 分钟开始做题，
或 3D 分钟等，但永远不要开始更短 - 运行
在更长的运行之前出现问题。
这让我想起了 Huffman coding。
我不确定下面的方法是否最优，但在实践中它可能会给出一个很好的答案。
- 选择最简单的两个问题 T0 和 T1，并将它们替换为由时间 D+max(T0,T1) 组成的单个问题。
- 重复直到剩下一个问题
如果将问题存储在二进制堆中，则可以在 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
问题陈述的解释部分有些含糊不清。根据语句的解释方式，可能有以下解决方案：
如果假设你可以在D分钟内解释N道题，那么解释一道题需要N/D分钟。我们称其为 Te，因为 "time to explain"。而解决问题 i 的时间是 Ti，我们知道这等于 i 分钟。
所以在比赛开始时，成员 1（知道所有问题）向成员 2 解释问题 N。这需要 Te 分钟。然后，成员 2 开始解决问题 N（需要 N 分钟才能解决），成员 1 开始向成员 3 解释问题 N-1。这一直持续到成员 1 向成员 N 解释问题 2。此时，成员 N 开始正在处理问题 2，成员 1 开始处理问题 1。
假设有 4 个问题，4 个团队成员，D=8。所以Te=2.
Time Description
0 Member 1 begins explaining Problem 4 to Member 2
2 Member 2 begins working on Problem 4
Member 1 begins explaining Problem 3 to Member 3
4 Member 3 begins working on Problem 3
Member 1 begins explaining Problem 2 to Member 4
6 Member 2 completes problem 4
Member 4 begins working on Problem 2
Member 1 begins working on Problem 1
7 Member 3 completes Problem 3
Member 1 completes Problem 1
8 Member 4 completes Problem 2
无论 D 或 N 的值如何，这似乎都是最佳解决方案：安排它以便尽可能早地开始解决花费时间最长的问题。
我怀疑问题陈述是用其他语言给出的问题的英文翻译，或者可能是对最初用英文编写并翻译成其他语言的内容的重新翻译。因为如果那是最初的问题陈述，那么应该禁止编写它的人再次编写问题。
完成任何一项任务所需的时间长度似乎具有 C * D + T, where C is a positive integer less than N 的形式，并且必须考虑所有 N-1 的提前期。假设我们犯了一个错误，最佳解决方案实际上应该有一个任务加上更长的交付时间——所以一些 C * D + Tj < C * D + Ti, where Ti < Tj，这是不可能的。
因此，对对的总和进行一次迭代（假设输入已排序）：
solution = maximum (T2 + (n-1) * D, T3 + (n-2) * D...D + Tn)