切換
舊版
前往
大廳
主題

ZeroJudge - e611: 11661 - Burger Time 解題心得

Not In My Back Yard | 2020-01-19 00:21:51 | 巴幣 0 | 人氣 145

題目連結:


題目大意:
輸入有多筆測試資料,每筆佔兩列。第一列給定一正整數 L (1 ≦ L ≦ 2000000),代表公路的長度;接著的一列給定一長度為 L 的字串,代表公路上的店家資訊。其中的字元可能是「R」、「D」、「Z」或是「.」,依序代表為有餐廳、有藥局、兩者皆有,以及兩者皆無。

試問公路上最靠近彼此的餐廳與藥局,兩者距離多少單位?



範例輸入:
2
RD
5
..Z..
10
.R......D.
10
.R..Z...D.
10
...D..R...
25
..D...R.RR...DD...D.R...R
0


範例輸出:
1
0
7
0
3
2


解題思維:
掃過字串,途中保持更新著上一個不是「.」的字元,並與現在的字元做比對。不一樣即代表兩者其中一個是餐廳,另一個是藥局。計算其距離去看看是不是當前最小。

但是如果當前字元是「Z」,則代表最近的距離必為 0 。

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

創作回應

更多創作