你聽過樓下的房客嗎?
據說,在一個遙遠的國度,有個名叫希爾伯特的人,收了無限多個房客。雖然希爾伯特的房間已經住滿了,然而這些房客住的房間編號是從0開始的全體非負整數,所以不管來了多少(可數個)房客,希爾伯特總是能收容他們,不過這又是另一個故事了。
話說有一次,希爾伯特煮了幾個鬆餅給前 $n$ 個房客吃,其中住在編號是 $i$ 的房客拿到了 $P_i$ 個鬆餅。然而這些鬆餅很容易就冷掉了,所以這些房客決定和其它房客共享鬆餅。在每一分鐘,每個房客可以吃掉一個鬆餅,或者分一些些鬆餅給另一個房客(不一定要是前 $n$ 個房客)。然而希爾伯特並不喜歡自己的好意一直不斷地被這樣分發掉(看起來他很傲嬌),所以他規定房客們分鬆餅的總次數不能超過一個數 $B$ 。儘管如此,這些房客還是想要在最快的時間內將鬆餅吃完。然而,無窮多個人聚在一起討論是一件非常麻煩的事,所以這些人拜託你,希爾伯特的學生,解決他們的煩惱。
如果你失敗的話,你會被無限多個人圍毆至死。
如果你成功的話,你會解出希爾伯特的第三個問題。
第一行有兩個整數 $1\leq n\leq 10^ 5, 0\leq B\leq 10^ 6$,代表前 $n$ 個房客拿到了鬆餅而且他們總共只能分鬆餅 $B$ 次。
緊接著的一行有 $n$ 個正整數 $P_0, P_1,\dots, P_{n-1}$ ,其中 $P_i\leq 10^ 6$ 代表第$i$個人拿到的鬆餅數。
子任務(測資) | 額外限制 | 分數 |
1 (0~4) | $B\leq 25$ | 13 |
2 (5~9) | $B\leq 75$ | 12 |
3 (10~14) | 無限制 | 75 |
請輸出一行代表所有鬆餅最快能在幾分鐘內吃完。
一種在五分鐘內吃完的方法:
第一分鐘時編號0, 1的房客吃一個鬆餅,編號2的房客分給編號3的房客三個鬆餅。
第二分鐘時編號0,1,3的房客吃一個鬆餅,編號2的房客分給編號4的房客三個鬆餅。
接下來的時間大家都自己吃自己的鬆餅。
Problem set / Description by Paupière
建國中學105學年度校內第一次模擬賽pE
題目取自2015 TOI第二階段選訓第三次模擬考pC
No. | Testdata Range | Score |
---|---|---|
1 | 0~4 | 13 |
2 | 5~9 | 12 |
3 | 10~14 | 75 |