切換
舊版
前往
大廳
主題

ZeroJudge - c198: 保持穩定供電 解題心得

Not In My Back Yard | 2018-09-22 16:33:13 | 巴幣 0 | 人氣 159

題目連結:


題目大意:
給定兩正整數N、X(3 ≦ N ≦ 500,2 ≦ X ≦ N),N表示有1~N戶人家,其中第X戶為市長家。

現從第1戶家開始斷電,接下來數M戶(已斷電的不予記數,數到超過N戶,便回頭從1開始數),數到的第M戶,將其斷電。(M ≧ 2)

求其他N-1戶人家都斷電,只有市長還有電力之最小的M值為何?


解題思維:
經典的Josephus問題,只是這題只要用迴圈去跑,並模擬即可解決。

把當前的停電狀況存在一個陣列裡,並從一開始就把「1」設為「停電」的狀態(可以一個布林值陣列)。

接下來從M = 2開始,模擬出會發生的情況。當中,每遇到停電的一戶人家,就跳過不數,值到數滿M戶。

以上模擬只要剩下一戶人家或是市長家(也就是X)被斷電了,馬上跳出來。並判斷是否只剩下一戶人家,是的話,此刻的M就是我們要的答案;反之,就繼續下一個M值。



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

創作回應

相關創作

更多創作