search

KyrieSu / Code_cpp

0 stars 0 forks source link

001.螞蟻愛亂爬 #1

Open LarryLuTW opened 8 years ago

LarryLuTW commented 8 years ago

內容:

一根長度 L 公分的木棍 上面有 n 隻螞蟻 每支螞蟻會向左爬或向右爬 速度都是 1 公分/秒 兩螞蟻相撞則兩隻都轉身朝各自的反方向前進

若已知每支螞蟻的初始位置及方向 計算要經過幾秒之後所有的螞蟻都能爬出木棍

輸入說明:

第一行為螞蟻數量 n 及木棍長度 L 接下來的每一行是每一支螞蟻的位置 x 及方向 d x 代表該螞蟻離木棍左端的距離 d 代表方向(0 表示向左, 1 表示向右)

n <= 10^5 L <= 10^6

輸出說明:

需要多少時間 才能讓所有螞蟻爬出木棍

範例輸入:

4 10
1 0
3 1
5 0
7 1

範例輸出:

7
KyrieSu commented 8 years ago

v1 (my version)

開一個struct裡面有x,v分別表示起始位置和方向，再用一個set紀錄樹枝上面還有幾隻螞蟻，並跑兩層迴圈，外層為秒數，內層為螞蟻，如果相撞就交換v，並順便判斷有沒有到終點。 時間複雜度：O(N*L)

v2 (smart version)

不需要調頭，因為AB兩隻螞蟻即時調頭了，走得距離也是一樣，所以只需要繼續走，感覺像是換了靈魂一樣XD 所以我們只需要計算誰離終點比較遠即可。 時間複雜度：O(N)

LarryLuTW commented 8 years ago

我剛剛看了螞蟻的 code 還滿棒的