#45384: 需要約國一數學以及基本迴圈處理


racham.chen@gmail.com (Dan Chen)

學校 : 不指定學校
編號 : 217061
來源 : [114.47.84.135]
最後登入時間 :
2022-12-04 21:38:07
q181. 1. 等紅綠燈 -- 2025年1月APCS | From: [114.47.66.90] | 發表日期 : 2025-02-23 00:09

分析題意可知道題目的需求是這樣:
1. 有n個小孩騎一圈所需時間
2. 有綠燈和紅燈持續時間,並且紅綠燈會交替出現,綠燈先開始
3. 計算這n個小孩需要等待紅燈的時間

解法分析:
基本上,我們可以用每一個小孩除以紅燈+綠燈時間的餘數去破解這題
因為每次紅燈+綠燈經過一輪,小孩沒有到,就要去看下一輪,還沒到就要繼續看下一輪,依此類推
這就讓我們發現,一直扣除紅燈+綠燈時間直到小於這個值,剩下的時間就足以決定這個小孩的等待時間
這個剩下的時間正好就是: 
小孩騎一圈的時間除以紅燈+綠燈時間的餘數

接下來想看看這個剩下的時間為多少時,小孩必須等待紅燈
答案是: 若剩下時間大於等於綠燈時間
因為這樣綠燈的時間已經走完了,但紅燈還沒
所以可以分析出一個條件判斷:
1. 若剩下時間<綠燈時間 => 不須等待
2. 若剩下時間>=綠燈時間 => 需要等待 紅燈時間 - (剩下時間 - 綠燈時間) = 紅燈時間 + 綠燈時間 - 剩下時間

題目輸入第二行給定小孩的數目n,我們可以用一個陣列大小為n的陣列儲存
然後利用C++ cin的機制,寫下這個架構的迴圈處理:
while(cin >> child){
...
}

然後依照上面分析寫下if 若剩下時間>=綠燈時間 => 需要等待 然後累加到存答案的變數裡面(初始為0)這樣的解法 時間複雜度: O(n) 空間複雜度: O(n))

實際上也可以不用陣列儲存
直接把後續判斷和累加寫道我上面的while迴圈的區塊裡
這樣可以讓空間複雜度為O(1)

 
ZeroJudge Forum