設pos[5]={1,2,5,7,8}

1. greedy

greedy的想法就是:

最前面的點一定會是在第一座基地台的左邊界，除了這樣以外的放法，對於這個題目沒有任何幫助。

所以pos[0]+dis(dis=基地台的直徑)就會是第一個基地台所涵括的距離(pos[0]~pos[0]+dis)

所以(pos[0]~pos[0]+dis)這段距離以內的所有點都不用再處裡。

再來，自第一個基地台右邊界，可能還有一段距離才會有下一個尚未被覆蓋到點。

所以這個點就是，上一個基地台的最右邊含括到的點再往右一個。

再來就按照這個規律去greedy啦~

2. binary search

看題目可以知道，最小的基地台直徑就是1，而最大的直徑就會是(pos[4]-pos[0])/k

(所有基地台的總範圍覆蓋整張地圖，至於為什麼這就是最壞解，可以思考一下，有些解中間可能會有地方不會被涵蓋到)

然後我們就會根據上面觀念設計一個函式從1開始窮舉基地台直徑，判斷這樣的基地台直徑是否能夠達成題目的要求

這樣做觀念是對的，但是會TLE~~

觀察一下，會發現基地台直徑與基地台數量具有單調性(基地台數量愈少，基地台直徑就會增加)

然後根據上面，我們知道直徑的最大、最小值，所以就可以對題目做二分搜啦~~~~

會有這些想法，對我來說很多都是來自平常的刷題啦，可能國文不好的很難讀懂我這篇QQ

建議搭配其他兩篇解題報告服用

設pos[5]={1,2,5,7,8}

1. greedy

greedy的想法就是:

最前面的點一定會是在第一座基地台的左邊界，除了這樣以外的放法，對於這個題目沒有任何幫助。

所以pos[0]+dis(dis=基地台的直徑)就會是第一個基地台所涵括的距離(pos[0]~pos[0]+dis)

所以(pos[0]~pos[0]+dis)這段距離以內的所有點都不用再處裡。

再來，自第一個基地台右邊界，可能還有一段距離才會有下一個尚未被覆蓋到點。

所以這個點就是，上一個基地台的最右邊含括到的點再往右一個。

再來就按照這個規律去greedy啦~

 

2. binary search

看題目可以知道，最小的基地台直徑就是1，而最大的直徑就會是(pos[4]-pos[0])/k

(所有基地台的總範圍覆蓋整張地圖，至於為什麼這就是最壞解，可以思考一下，有些解中間可能會有地方不會被涵蓋到)

然後我們就會根據上面觀念設計一個函式從1開始窮舉基地台直徑，判斷這樣的基地台直徑是否能夠達成題目的要求

這樣做觀念是對的，但是會TLE~~

 

觀察一下，會發現基地台直徑與基地台數量具有單調性(基地台數量愈少，基地台直徑就會增加)

然後根據上面，我們知道直徑的最大、最小值，所以就可以對題目做二分搜啦~~~~

 

會有這些想法，對我來說很多都是來自平常的刷題啦，可能國文不好的很難讀懂我這篇QQ

建議搭配其他兩篇解題報告服用

感謝大哥 過關了 雖然很慢
"最前面的點一定會是在第一座基地台的左邊界，除了這樣以外的放法，對於這個題目沒有任何幫助。"