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

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

Problem Statement

題目簡述

給定 nn 天，每一天有固定數量的教室可供借用，第 ii 天可借用的教室數量為 rir_i。

同時有 mm 個訂單，每個訂單包含三個整數 (di,li,ri)(d_i, l_i, r_i)，表示需要從第 lil_i 天到第 rir_i 天每天借用 did_i 間教室。

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

Constraints

約束條件

  • 1≤n,m≤1061 \le n, m \le 10^6
  • 0≤ri,di≤1090 \le r_i, d_i \le 10^9
  • 1≤li≤ri≤n1 \le l_i \le r_i \le n

思路：二分答案 + 差分

問題核心與單調性

我們需要按順序處理訂單，並找出第一個失敗的位置。如果前 k 個訂單全部可行，那麼前 k-1 個訂單當然也可行；反之，如果第 k 個訂單失敗，則第 k+1 個訂單也必定失敗（因為累積的教室用量只會更多）。

這是一個典型的單調性質——可行與不可行之間存在一個明確的分界點。

如何利用單調性？

我們可以二分搜尋這個分界點：猜測一個訂單編號 mid，檢查前 mid 個訂單是否全部能被滿足。如果不是，則答案在左半邊；如果是，則繼續向右尋找。

檢查函數的設計

如果暴力地逐一對每個訂單的每一天進行操作，時間複雜度為 O(m×n)O(m \times n)，完全不可行。

注意到每筆訂單實際上是對一個區間 [li,ri][l_i, r_i] 內的每天增加 did_i 的需求。這種「區間加法」的操作非常適合使用差分陣列來優化。

關鍵洞察

差分陣列能在 O(m+n)O(m + n) 的時間內完成同時 apply 多個區間加法的查詢，非常適合這種「只問最終狀態，不問中間過程」的題型。

複雜度分析

  • 時間複雜度：O((n+m)log⁡m)\mathcal{O}((n + m) \log m)，二分 log⁡m\log m 次，每次檢查 O(n+m)\mathcal{O}(n + m)。
  • 空間複雜度：O(n+m)\mathcal{O}(n + m)，主要為差分陣列與訂單資料儲存。

Code

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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()