前往
大廳
主題

ZeroJudge - f408: 迷你蘋菓鎮 解題心得

Not In My Back Yard | 2021-07-12 00:00:06 | 巴幣 0 | 人氣 170

題目連結:


題目大意:
輸入第一列給定一正整數 n(1 ≦ n ≦ 1000),代表有 n 個門牌號碼。第二列給定 n 個整數(值介於 -46000 和 46000 之間),其中負數為白人家庭、正數代表著黑人家庭,而絕對值為門牌號碼之值。

由於先前的爭議事件,鎮長決定在每個相鄰黑人、白人家庭之間設立一個巡邏站。試問需要建立幾個巡邏站?



範例輸入:
範例輸入 #1
3
1 3 -5

範例輸入 #2
4
-9 -5 -1 3


範例輸出:
範例輸出 #1
1

範例輸出 #2
2


解題思維:
將 n 個門牌號碼按照絕對值大小由小排到大(或是由大排到小),然後掃過每個相鄰數對。然後相鄰數對的數字中,一者為正數、一者為負數,則需要在這兩個家庭之間設立一個巡邏站。因此便可以找到所需的巡邏站數量。




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

創作回應

更多創作