題目連結:
題目大意:
輸入第一列給定一正整數 n(1 ≦ n ≦ 1000),代表有 n 個門牌號碼。第二列給定 n 個整數(值介於 -46000 和 46000 之間),其中負數為白人家庭、正數代表著黑人家庭,而絕對值為門牌號碼之值。
由於先前的爭議事件,鎮長決定在每個相鄰黑人、白人家庭之間設立一個巡邏站。試問需要建立幾個巡邏站?
範例輸入:
範例輸入 #1
3
1 3 -5
範例輸入 #2
4
-9 -5 -1 3
範例輸出:
範例輸出 #1
1
範例輸出 #2
2
解題思維:
將 n 個門牌號碼按照絕對值大小由小排到大(或是由大排到小),然後掃過每個相鄰數對。然後相鄰數對的數字中,一者為正數、一者為負數,則需要在這兩個家庭之間設立一個巡邏站。因此便可以找到所需的巡邏站數量。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。