🔗 AWC0096C Watering the Flower Bed

Problem Statement

題目簡述

有一個由 $N$ 個區段組成的花壇，第 $i$ 段目前濕度為 $A_i$ ，目標濕度為 $B_i$ 。
一次操作可以選擇一段長度恰好為 $K$ 的連續區間，將其中每個區段的濕度都增加 $1$ 。
可以操作任意次，問能否讓所有區段的濕度都剛好變成目標值；若可以，輸出最少操作次數，否則輸出 $-1$ 。

Constraints

約束條件

$1 \le K \le N \le 3 \times 10^5$
$0 \le A_i \le 10^9$
$0 \le B_i \le 10^9$
輸入皆為整數
若可以達成目標，最小操作次數保證不超過 $3 \times 10^{14}$

思路：由左到右貪心 + 差分

先把問題從「濕度」改寫成「每段還需要增加多少」。令 $C_i=B_i-A_i$ ，表示第 $i$ 段距離目標還差多少水量。因為操作只能增加，若存在 $C_i<0$ ，代表某一段目前已經超過目標，那就不可能再修回來，直接輸出 $-1$ 。

接著要處理的是：從全 $0$ 的狀態開始，每次可以對長度固定為 $K$ 的區間整體 $+1$ ，能否剛好湊出這個差值陣列 $C$ ，並且操作次數最少。

貪心策略

從左到右掃描，遇到還有缺少水量的區段，就立刻補足以 $i$ 為起點的連續 $K$ 個區段。因為 $i$ 左邊的位置已經處理完畢，不會再有操作能覆蓋到 $i$ ，因此這是唯一的選擇。若掃到某個區段時已經無法放下長度 $K$ 的區間（ $i > N - K$ ），則無解。

為什麼可以從左到右貪心？

看最左邊尚未處理的位置。能影響它的操作，起點只能在它自己或更左邊；但更左邊的位置已經被處理完，不能再被改動。所以到了目前位置時，如果它還少了某個水量，就只剩下一種選擇：從目前位置開始補足這些水量。

這個選擇沒有自由度，也不會漏掉更好的答案。因為少補會讓目前位置不達標，多補會讓目前位置超標；剛好補足是唯一可能的做法。

固定長度區間加法常見模型：從左到右掃描時，當前位置的需求一旦確定，就必須在這裡決定是否開啟新的區間操作。後面的位置不能回頭修前面。

用差分維護目前已經增加多少

前置知識：差分陣列

如果要對一段連續區間 $[l,r]$ 全部加上 $x$ ，不必真的逐格修改。可以在左端點記錄「從這裡開始多 $x$ 」，在右端點後一格記錄「從這裡開始少 $x$ 」。之後從左到右累加這些變化量，就能還原每個位置實際被加了多少。

注意到一次操作的影響是長度固定的連續區間：從起點開始生效，到起點加上 $K$ 的位置失效。這正好是差分擅長維護的資訊。因此我們不用真的更新整段，只要維護目前仍然有效的總增加量；當在目前位置新增若干次操作時，立刻把它加入當前貢獻，並在 $K$ 格之後記錄一個相反變化，表示這批操作到那裡就失效。

無法操作的兩種情況

某段已經超過目標濕度（ $s_i > C[i]$ ）
掃描到某段時，還需要補水（ $s_i < C[i]$ ），但已經無法放下長度 $K$ 的區間（ $i > N - K$ ）

正確性說明

若一路掃描到最後都沒有失敗，每個位置都被唯一且剛好地補到目標值。由於每次在目前位置只做「不得不做」的操作，所以得到的操作次數也是最小值。

複雜度分析

時間複雜度： $\mathcal{O}(N)$
空間複雜度： $\mathcal{O}(N)$

類題

類似題目

Code

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    C = [b - a for a, b in zip(A, B)]
    if any(c < 0 for c in C):
        print(-1)
        return

    ans = s = 0
    diff = [0] * (N + 1)
    for i, c in enumerate(C):
        s += diff[i]
        need = c - s
        if need < 0 or need > 0 and i + K > N:
            print(-1)
            return
        if need > 0:
            ans += need
            s += need
            diff[i + K] -= need
    print(ans)


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.