java - ACM ICPC编程竞赛问题

Question

这个问题已经有答案了:

已关闭 12 年前。

Possible Duplicate:
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之后的元素递归调用相同的函数

这将在飞机预定窗口的限制内平均分配可用时间。

一旦你有了大致均匀分布的窗口，选择最小的窗口并用它的相邻平面测试它，看看它们是否可以移动一些来扩展最小的窗口。重复此过程，直到最小的窗口不能发生显着的移动。