分析題意可知道題目的需求是這樣:
1. 有n個小孩騎一圈所需時間
2. 有綠燈和紅燈持續時間,並且紅綠燈會交替出現,綠燈先開始
3. 計算這n個小孩需要等待紅燈的時間
解法分析:
基本上,我們可以用每一個小孩除以紅燈+綠燈時間的餘數去破解這題
因為每次紅燈+綠燈經過一輪,小孩沒有到,就要去看下一輪,還沒到就要繼續看下一輪,依此類推
這就讓我們發現,一直扣除紅燈+綠燈時間直到小於這個值,剩下的時間就足以決定這個小孩的等待時間
這個剩下的時間正好就是:
小孩騎一圈的時間除以紅燈+綠燈時間的餘數
接下來想看看這個剩下的時間為多少時,小孩必須等待紅燈
答案是: 若剩下時間大於等於綠燈時間
因為這樣綠燈的時間已經走完了,但紅燈還沒
所以可以分析出一個條件判斷:
1. 若剩下時間<綠燈時間 => 不須等待
2. 若剩下時間>=綠燈時間 => 需要等待 紅燈時間 - (剩下時間 - 綠燈時間) = 紅燈時間 + 綠燈時間 - 剩下時間
題目輸入第二行給定小孩的數目n,我們可以用一個陣列大小為n的陣列儲存
然後利用C++ cin的機制,寫下這個架構的迴圈處理:
while(cin >> child){
...
}
然後依照上面分析寫下if 若剩下時間>=綠燈時間 => 需要等待 然後累加到存答案的變數裡面(初始為0)這樣的解法 時間複雜度: O(n) 空間複雜度: O(n))
實際上也可以不用陣列儲存
直接把後續判斷和累加寫道我上面的while迴圈的區塊裡
這樣可以讓空間複雜度為O(1)