切換
舊版
前往
大廳
主題

ZeroJudge - b878: Radius 半徑 解題心得

Not In My Back Yard | 2018-10-03 15:58:40 | 巴幣 2 | 人氣 177

題目連結:


題目大意:
給定一個正整數N(N ≦ 1, 000, 000),代表接下來有N個彼此不重複的數字,而這N個數字按照順序排成一直線。

並定義半徑為:對於每一格而言,邊際離此格多遠,或是比本格數字小的最近的那個格子有多遠(看哪個數字比較小),即是這格的「半徑」。

求這串數字的半徑和為多少。


解題思維:
可以先把每一格的半徑先初始化成非常大的數字。

然後對於每一格而言,就用迴圈去「擴張」,一次一格。一遇到比自己小的數字,或是碰到邊邊了,當前擴張多少格,半徑就是多少。(左右兩邊要同時擴張喔)

而在「擴張」的途中,若是遇到比自己大的數字,可以把那格數字的半徑先變為彼此的距離。這樣迴圈在跑到那格的時候,通常就不用再跑一次了。



此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作