題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🌈 AWC0096B Adventurer’s Staircase

Problem Statement

題目簡述

高橋要從 11 樓一路爬到 NN 樓。第 11 到第 N−1N-1 樓各有一隻怪物，第 ii 樓怪物強度為 EiE_i，第 NN 樓沒有怪物。

若當前戰鬥力至少為怪物強度，就能擊敗怪物並吸收其力量，使戰鬥力增加該怪物強度；否則冒險失敗。進入迷宮前可以使用 00 到 KK 瓶強化藥水，每瓶讓初始戰鬥力增加 11，途中不能再使用。

初始戰鬥力為 SS。求能抵達 NN 樓所需的最少藥水數；若最多使用 KK 瓶仍無法抵達，輸出 −1-1。

Constraints

約束條件

  • 2≤N≤2×1052 \le N \le 2 \times 10^5
  • 1≤S≤1091 \le S \le 10^9
  • 0≤K≤10180 \le K \le 10^{18}
  • 1≤Ei≤1091 \le E_i \le 10^9
  • 輸入皆為整數。

思路：把藥水數變成最大缺口

這題看起來可以二分需要喝的藥水數，並模擬每一層是否能打過。但其實不需要二分，也不需要反覆模擬。

注意到藥水只能在出發前使用，且每瓶藥水都會對後面每一層的戰鬥力產生同樣的固定增量。

先不考慮藥水。抵達某一層並開打前，戰鬥力等於初始戰鬥力加上前面已擊敗怪物的強度總和。如果這個值不夠打當前怪物，那麼缺多少，就至少需要在一開始補多少瓶藥水。

所以每一層都會給出一個下界：

第 i 層缺口=max⁡(0,Ei−(S+∑j=1i−1Ej))\text{第 } i \text{ 層缺口} = \max\left(0, E_i - \left(S + \sum_{j=1}^{i-1} E_j\right)\right)

要讓所有樓層都能通過，只要滿足所有下界，也就是取最大缺口即可。若某些樓層本來就打得過，缺口是負數或零，對答案沒有貢獻。

若最大缺口不超過 KK，它就是最少藥水數；否則即使用完所有藥水也無法通關，輸出 −1-1。

複雜度分析

  • 時間複雜度：O(N)\mathcal{O}(N)
  • 空間複雜度：O(N)\mathcal{O}(N)，目前實作建立前綴累積陣列；若邊掃描邊維護目前戰鬥力，可降為 O(1)\mathcal{O}(1)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from itertools import accumulate


def solve():
    N, S, K = map(int, input().split())
    A = list(map(int, input().split()))
    assert len(A) == N - 1

    ps = list(accumulate(A, initial=S))

    need = max(x - s for x, s in zip(A, ps))
    print(max(0, need) if need <= K else -1)


if __name__ == "__main__":
    solve()

寫在最後

Cover Image Credit

The cover image was created by @Qurami. All rights belong to the original artist.

It is used here only as a non-commercial cover illustration for this note. I do not claim ownership of the artwork.

If you are the copyright holder and believe this usage is inappropriate, please contact me by email or leave a comment. I will remove the image promptly.