🔗 P1083 [NOIP 2012 提高组] 借教室

Problem Statement

題目簡述

給定 $n$ 天，每一天有固定數量的教室可供借用，第 $i$ 天可借用的教室數量為 $r_i$ 。

同時有 $m$ 個訂單，每個訂單包含三個整數 $(d_i, l_i, r_i)$ ，表示需要從第 $l_i$ 天到第 $r_i$ 天每天借用 $d_i$ 間教室。

按訂單順序處理，當某個訂單無法滿足（即某一天剩餘教室數不足）時，該訂單及之後的所有訂單都無法執行。
請找出第一個無法滿足的訂單編號，若全部滿足則輸出 0。

Constraints

約束條件

$1 \le n, m \le 10^6$
$0 \le r_i, d_i \le 10^9$
$1 \le l_i \le r_i \le n$

思路

方法一：二分答案 + 差分

從暴力到二分

先看最直覺的做法：對每個訂單，在 $[l, r]$ 範圍內每天加上 $d$ ，然後掃描 $n$ 天檢查是否超出容量。 $O(nm)$ ， $10^6 \times 10^6$ 完全不行。

瓶頸在哪？倒不是在於檢查本身，而是反覆做太多次。但先別急著優化檢查——先看看能不能減少檢查的次數。

單調性

設 $f(k)$ =「前 $k$ 個訂單是否全部合法」，則 $f(k)$ 在 $[0, m]$ 上滿足：存在一個分界點 $p$ ，使得 $k \le p$ 時 $f(k)$ 為 true， $k > p$ 時為 false。

原因很簡單：多接一個訂單，每天的總需求只會增加或持平，不可能讓原本超標的變成不超標。

問題變成：在 $[0, m]$ 上二分搜尋最後一個 $f(k) = \text{true}$ 的位置。二分框架：

$f(\text{mid})$ 為 true → 答案在 $[\text{mid}, m]$ ，左邊界右移
$f(\text{mid})$ 為 false → 答案在 $[0, \text{mid}-1]$ ，右邊界左移

最後第一個失敗的即為左邊界（若仍在 $[1, m]$ 範圍內），否則全可行輸出 $0$ 。

檢查函數：用差分處理區間加法

剩下來的問題是：給定 $k$ ，如何快速判斷前 $k$ 個訂單是否合法？

每個訂單是對一個區間 $[l, r]$ 每天加 $d$ 。這種「多次區間加法後查詢最終狀態」的操作，標準做法就是差分陣列。

差分陣列模板

對 $[l, r]$ 同時 $+v$ 等價於 diff[l] += v、diff[r+1] -= v。做完所有區間操作後，對差分陣列做一次前綴和，每個位置就還原成實際值。時間 $O(k + n)$ 。

對比暴力：暴力是每個訂單 $O(r-l)$ 逐天加，差分是每個訂單 $O(1)$ 。瓶頸直接被消掉。

複雜度分析

時間複雜度： $\mathcal{O}((n + m) \log m)$ ，二分迭代 $\log m$ 次，每次檢查 $O(n + m)$
空間複雜度： $\mathcal{O}(n + m)$ ，差分陣列 + 訂單資料

方法二：雙指針反向撤銷

二分用了

\log m

次檢查。能不能線性掃一次就找到答案？

換個思路

方法一的本質是：每次二分試探一個 $k$ ，需要重新用差分檢查前 $k$ 個。這就像是反覆「從零開始疊訂單」。

方法二換成反面操作：一次性把全部 $m$ 個訂單套上差分，然後逐天掃描。遇到某天教室不夠用了，就從「最後一個尚未被撤銷的訂單」往回取消——取消一個，當日的需求就往下掉一點，掉到不超標為止。

為什麼從後往前撤銷不會算錯

第 $i$ 天教室不夠，必須棄掉至少一個覆蓋第 $i$ 天的訂單。越晚的訂單，能影響的日期範圍越往後——棄掉它對「已經檢查過的前幾天」完全無影響，不會造成「前面天數本來已過關卻因撤銷而多出餘裕」的過度修正。

具體推導

設一個指標指向目前「最後一個還沒被撤銷」的訂單，初始為 $m-1$ （0-indexed）。

逐日累加差分前綴和得到當日需求。如果需求超過容量，進入撤銷階段：

取出當前指標指向的訂單，把它的差分效應還原（diff[l] -= d、diff[r+1] += d）
如果這筆訂單的區間 $[l, r]$ 覆蓋了當前這一天，當日需求也要立即扣掉這筆訂單的量。因為差分還原只會影響之後尚未掃描的天數——對「正在處理的今天」，前綴和早已算出，不會自動回溯
指標左移一位（代表這筆訂單被捨棄），繼續檢查需求是否仍超標，若是則繼續撤銷

常見錯誤

忘記手動扣減當前這一天的需求量。差分還原改的是 diff[l] 和 diff[r+1]，但當前這一天的 s 是之前不斷累加而成的，差分陣列的修改不會回過頭去更新它。對於 $l \le i \le r$ 的訂單，必須手動 s -= d。

掃描結束後：若指標仍為 $m-1$ （沒撤銷過任何訂單），輸出 $0$ ；否則第一個失敗的訂單是 指標 + 2（0-indexed 的指標 + 1 是第一筆被撤銷的，轉 1-based 輸出）。

複雜度分析

時間複雜度： $\mathcal{O}(n + m)$ ，每個訂單最多被加入一次、撤銷一次，每筆撤銷 $O(1)$
空間複雜度： $\mathcal{O}(n + m)$ ，差分陣列 + 訂單資料（方法一不會同時持有全部訂單的差分，方法二需要先全量建構後再撤銷，空間等同）

類題

🟡 3356. Zero Array Transformation II

Code

方法一：二分答案 + 差分

本題的空間對 Python 來說有些壓力，需要使用 array 搭配原地清零，避免使用 list 以及重新分配陣列。

from array import array


def solve():
    n, m = map(int, input().split())
    A = array("l", map(int, input().split()))

    D = array("l", [])
    L = array("l", [])
    R = array("l", [])
    for _ in range(m):
        d, l, r = map(int, input().split())
        D.append(d)
        L.append(l - 1)
        R.append(r - 1)

    diff = array("l", [0] * (n + 1))

    def check(mid: int) -> bool:
        # 重置差分陣列
        for i in range(n + 1):
            diff[i] = 0
        # 套用前 mid 個訂單的區間增加
        for i in range(mid):
            d, l, r = D[i], L[i], R[i]
            diff[l] += d
            diff[r + 1] -= d
        # 前綴和還原每日用量
        for i in range(1, n):
            diff[i] += diff[i - 1]
        # 檢查是否超出容量
        return all(diff[i] <= A[i] for i in range(n))

    left, right = 0, m
    while left <= right:
        mid = (left + right) // 2
        if check(mid):
            left = mid + 1
        else:
            right = mid - 1
    # left 是第一個失敗的訂單編號（1-based）
    if left <= m:
        print(-1, left, sep="\n")
    else:
        print(0)


if __name__ == "__main__":
    solve()

方法二：雙指針反向撤銷

from array import array


def solve():
    n, m = map(int, input().split())
    A = array("l", map(int, input().split()))
    D = array("l", [])
    L = array("l", [])
    R = array("l", [])
    for _ in range(m):
        d, l, r = map(int, input().split())
        D.append(d)
        L.append(l - 1)
        R.append(r - 1)

    diff = [0] * (n + 1)
    for d, l, r in zip(D, L, R):
        diff[l] += d
        diff[r + 1] -= d

    s = 0
    k = m - 1
    for i, x in enumerate(A):
        s += diff[i]
        while k >= 0 and s > x:
            v, l, r = D[k], L[k], R[k]
            diff[l] -= v
            diff[r + 1] += v
            if l <= i <= r:
                s -= v
            k -= 1
        if s > x:
            break

    if k < m - 1:  # 有不能被滿足的需求
        print(-1)
        print(k + 2)  # k + 1 是第一個不能被滿足的需求，轉換為 1-index 後是 k + 2
    else:
        print(0)


if __name__ == "__main__":
    solve()