Google Code Jam 2010 Qualification C

Problem C: Theme Park

Question: http://code.google.com/codejam/contest/dashboard?c=433101#s=p2&a=2
Answer: http://code.google.com/codejam/contest/dashboard?c=433101#s=a&a=2

這題是最後一題, 應該也算是最簡單的一題

不過有點Tricky, 想答對Large的難度, 要做點最佳化才有辦法

題目是說, 一般遊客去做雲霄飛車的時候, 都習慣一群一群人一起坐上去, 如果有人做不上去的話, 就會等下一班車. 然後, 每個人坐一次會付1元, 我們要算出雲霄飛車一天可以賺多少錢.

例如:

雲霄飛車有 6 個位置, 每天會開 4 次, 遊客有 4 群人, 每群遊客依序有 1, 4, 2, 1 人, 而這些遊客會整天一直排隊坐雲霄飛車.

所以, 第一次雲霄飛車會載 [1, 4] 人 (因為不能插隊, 所以不會把後面一個人的往前補)

第二次會載 [2, 1, 1] 人

第三次會載 [4, 2] 人

最後一次會載 [1, 1, 4] 人

因此, 最後一共賺了 21 元

在解法的方面, 應該都大同小異

我是用一個 Array 存了遊客人數 [1, 4, 2, 1]

另外還有一個相對應的快取 Array 存了計算過的結果 [5, 6, 4, 6]

快取Array, 初始為[?, ?, ?, ?] 
第一次載完 [1, 4] 人, 所以是 [5, ?, ?, ?]
第二次由第三群遊客開始, 載完 [2, 1, 1] 人, 所以是 [5, ?, 4, ?]
第三次載完 [4, 2] 人, 所以是 [5, 6, 4, ?]
第四次載完 [1, 1, 4] 人, 所以是 [5, 6, 4, 6]
第五次之後, 就不需要再計算, 而是直接使用快取的結果
速度上來說, 已經足以解決這個問題

官方提供了三種最佳化, 有興趣的人可以在上去看看