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

回答