Posted on 2011-01-23 13:20
Onway 閱讀(351)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
傷不起的ACM
題意：在x軸上方，給出n個(gè)點(diǎn)的xy坐標(biāo)，在x軸上安放的一點(diǎn)可以以半徑為d產(chǎn)生覆蓋，問(wèn)在x軸上至少要安放幾個(gè)點(diǎn)才可以將x軸上方的點(diǎn)都覆蓋起來(lái)。如果不能將全部的點(diǎn)覆蓋，那么輸出-1。
類型：貪心
思路：如果上方的某個(gè)點(diǎn)S能進(jìn)行覆蓋，那么肯定這個(gè)點(diǎn)在x軸上能夠確定一個(gè)范圍，在這個(gè)范圍安放的任何一個(gè)點(diǎn)都能將S覆蓋。n個(gè)點(diǎn)可以產(chǎn)生n個(gè)范圍，將這些范圍的起點(diǎn)按x軸排序從左到右進(jìn)行排序，注意這些范圍中相同起點(diǎn)而不同終點(diǎn)的排法，應(yīng)該是終點(diǎn)值較大的先排。排完以后，以第一個(gè)點(diǎn)的范圍開(kāi)始進(jìn)行貪心，在這個(gè)范圍能覆蓋的點(diǎn)都放進(jìn)來(lái)，注意更新這個(gè)覆蓋范圍，直到某個(gè)點(diǎn)不能進(jìn)行覆蓋為止，這時(shí)需要在x軸多安放一點(diǎn)了。
解析得真糟糕。其實(shí)就是將二維的覆蓋轉(zhuǎn)化為一維的覆蓋。
這個(gè)題目也想了一個(gè)多小時(shí)，主要是得到上面的思路比較曲折，自我感覺(jué)不太滿意。這個(gè)題目是轉(zhuǎn)到linxu系統(tǒng)上用vim寫的第一個(gè)題，也值得紀(jì)念一下。用g++編譯出來(lái)，一個(gè)編譯錯(cuò)誤。提交一次AC，gdb調(diào)試都不用，呵呵。