切換
舊版
前往
大廳
主題

ZeroJudge - b310: 英靈召喚 解題心得

Not In My Back Yard | 2020-06-25 17:44:58 | 巴幣 0 | 人氣 133

題目連結:


題目大意:
輸入第一列給定兩整數 N 、 M (0 < N ≦ 10 ^ 6 , 0 ≦ M ≦ 10 ^ 9),代表施放法術要 M 單位的魔力。接著一列給定 N 個整數 A1 ~ AN(皆介於 0 (含)~ 10 ^ 9 (含)之間),代表接著的 N 秒,土地每秒發出的魔力量之數值。

而蒐集魔力的時段必須是連續的不可中斷。試問,給定土地魔力的發出情況,最少幾秒可以集到至少 M 單位的魔力。如果無法集到 M 單位的魔力,則輸出「GGGGGZ」。



範例輸入:
6 8
1 3 2 4 0 3


範例輸出:
3


解題思維:
令 L = R = 1 ,代表從第一秒開始考慮。

每考慮一秒時,則現在 L ~ R 這個時段之魔力總合為 AL + AL+1 + …… + AR ,令該數 = S。如果 S - AL ≧ 所求魔力 M ,代表我們的時段可以更短,因此將 S 減去 AL 。然後再判斷一次,如果 S -  AL+1 仍 ≧ M ,則再減去……重複直到小於 M 。最後更新左端點 L 的值。

接著判斷當前的 S 是否 ≧ M ,如果符合則跟當前最短的時段 T (一開始初始化為等於 N 或是無窮大)去比較。如果現在這個時段(R - L + 1)比 T 短,則覆蓋掉 T 的值。

接著將 R 加上 1 ,考慮下一秒並重複以上步驟直到 R = N + 1 (代表結尾)。此時的 T 值即為所求最短的時段長。

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

創作回應

更多創作