主題

ZeroJudge - g420: PB.BAD question 解題心得

Not In My Back Yard | 2021-11-28 00:00:05 | 巴幣 0 | 人氣 38

題目連結:


題目大意:
輸入第一列給定兩整數 n 、 m(1 ≦ n ≦ 10 ^ 6,0 ≦ m ≦ 10 ^ 6),代表依序有 n 個關卡要過且初始血量為 m。

接著第二列給定 n 個整數,代表每個關卡會損失的血量值。第三列再給定 n 個整數,代表每個關卡結束並存活下來後會回復的血量值。

每個關卡只要扣完該關卡的損失後,血量值依舊不為負數便可以得到該關卡的回復量並繼續到下一個關卡(如果有的話)。

試問最遠可以抵達到哪個關卡(不一定要過關,在該關血量才變為負值也算)。



範例輸入:
5 4
3 5 2 4 1
4 0 1 0 5


範例輸出:
3


解題思維:
模擬即可。即掃過每個關卡時先扣除該關卡的損失,判斷當前血量是否為負數。如果是則輸出目前是第幾個關卡;反之,此時才將該關卡的回復量加到當前血量上。

如果所有關卡都通過了,則輸出關卡數之值即可(儘管測資中沒有可以通過所有關卡的情況發生)。

值得注意的是血量值有可能會超過 2 ^ 31 - 1,也就是有可能會超過 32 位元有號整數能儲存的範圍。因此需要宣告其為 64 位元有號整數,以免溢位。




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

創作回應

更多創作