2016年4月2日 星期六

TOI 3月份練習賽 懶人包

題目:

1. Card World : https://www.dropbox.com/s/7wehq59hqwgtjhy/Card%20world.pdf?dl=0
2. Loudspeaker : https://www.dropbox.com/s/2puwdvea84mgmdv/Loudspeaker.pdf?dl=0

第一題Card World :
基本上就是好好實作就好了XDDD
要小心陣列維度處理的問題

code : http://codepad.org/qP23deHx

第二題Loudspeaker :
認真想想,會發現他有二分搜的性質(如果ans可以,那ans+0.1, ans+0.2 ...也一定可以),那當我們確定二分搜可以之後呢,我們就要二分搜答案。

那要怎麼判斷當前距離ans是否可以呢?可以使用greedy的技巧,當現在可以覆蓋的面積沒有辦法覆蓋的pos[i]的家時,那我們就把一個喇叭放在pos[i] + ans的地方,讓覆蓋的距離延伸到pos[i] + 2 * ans

實作上還有一些些小細節,就看code自己想囉!

code : http://codepad.org/iEpS82wC


沒有留言:

張貼留言