3
的問題是在這裏：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2384公交車司機：UVA 11389
我設法用貪婪的方法來解決這個問題。我按降序排列早晨路線，晚上路線按升序排列，然後我在晚上路線中將早晨路線的最大值設定爲最小值。該解決方案已被接受。我試圖證明問題具有貪婪的選擇屬性，也就是說，貪婪的選擇是最佳解決方案的一部分。有人可以幫助證明。我只是在做這方面的證據的做法
http://cstheory.stackexchange.com/可能是一個更好的地方要問這個。 – 2012-01-27 17:34:09
@TomAnderson：cstheory是研究級別的問題。我懷疑這是一個。 – blubb 2012-01-27 17:44:15
此外，我注意到在問題中，工作限制和加班費率是用小時來描述的，但是長度是用米來描述的。噢，每天的限制是20個小時 - 我想孟加拉國的公交車司機是非常努力的！ – 2012-01-27 17:54:55