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