ACM ICPC程序设计竞赛问题

可能重复：
Can you answer this 2009 ACM International Collegiate Programming Contest Finals problem?ACM ICPC程序设计竞赛问题

嗨，

，并不能真正拿出一个很好的算法来解决它：

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

n = 3

，你给出的输入

0 10 
5 15 
10 15

答案是：7：30，平面之间的最大可能区间。

不太确定我会如何去解决这个问题。有小费吗？

2011-03-23 Xi Hao

编程竞赛的要点是测试你的编程技巧，而不是你的问题提问技巧...... – 2011-03-23 20:26:22

如此有帮助，安德鲁，谢谢:)我假设你意识到这个问题是两岁，我只是发布一个问题我我正在努力研究未来的竞争，是吗？ – 2011-03-23 20:28:28

http://stackoverflow.com/questions/1842587/can-you-answer-this-2009-acm-international-collegiate-programming-contest-finals – 2011-03-23 20:29:21

对于第一平面，选择最早的可能到达时间对于最后面，选择最新的可能到达时间

对于元件2通过元件N-1：

通过搜索一个中点平面分割元件1和元素n 之间的范围内（希望，那将是接近元件N/2）

recursivly要求元件1相同的功能和中点元件 recursivly调用相同的功能的元件船尾呃中点元素和元素n

这将平均划分在飞机计划窗口的约束范围内可用的时间。

一旦你有大致均匀间隔的窗口，选择最小的窗口，并用它的相邻平面测试它，看看它们是否可以移动一些来扩大最小的窗口。重复这个过程，直到最小的窗口不能移动一个可观的数量。

2011-03-23 20:34:54

回答