ACM ICPC程序设计竞争问题

Question

可能重复：

Can you answer this 2009 ACM International Collegiate Programming Contest Finals problem?

嗨,

我试图在这里做问题1-> http://cm.baylor.edu/ICPCWiki/attach/Problem%20Resources/2009WorldFinalProblemSet.pdf

也不能真正想出一个好的算法来解决这个问题：

基本上，有n个平面，n是从标准输入中读取的。然后，飞机可以到达的时间间隔为n个，您必须计算所有可能的平面之间的最大间隔。所以，说

n = 3

你就得到了输入

0 10
5 15
10 15

答案是: 7: 30，飞机之间最大的间隔时间。

不太确定我会怎么解决这个问题。有小费吗？

Answer 1

对于第一架飞机，选择最后一架飞机的最早到达时间，选择最新的可能到达时间。

元素2通过元素n-1：

通过将元素1和元素n之间的范围除以来搜索中点平面(希望这将接近元素n/2)

递归调用元素1的相同函数，中点元素递归在中点元素和元素n之后调用相同的函数。

这将在飞机预定窗口的约束下平均分配可用的时间。

一旦您有大致均匀的窗口，选择最小的窗口，并测试它的相邻平面，看看他们是否可以移动一些，以扩大最小的窗口。重复这个过程，直到最小的窗口无法移动一个显著的数量。