題目連結:
題目大意:
給定一個正整數N(N ≦ 1, 000, 000),代表接下來有N個彼此不重複的數字,而這N個數字按照順序排成一直線。
並定義半徑為:對於每一格而言,邊際離此格多遠,或是比本格數字小的最近的那個格子有多遠(看哪個數字比較小),即是這格的「半徑」。
求這串數字的半徑和為多少。
解題思維:
可以先把每一格的半徑先初始化成非常大的數字。
然後對於每一格而言,就用迴圈去「擴張」,一次一格。一遇到比自己小的數字,或是碰到邊邊了,當前擴張多少格,半徑就是多少。(左右兩邊要同時擴張喔)
而在「擴張」的途中,若是遇到比自己大的數字,可以把那格數字的半徑先變為彼此的距離。這樣迴圈在跑到那格的時候,通常就不用再跑一次了。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。