形式化题目

给定 $n$ 天，第 $i$ 天有 $r_i$ 个可租教室；再给定 $m$ 份按顺序处理的订单，第 $j$ 份订单 $(d_j, s_j, t_j)$ 要求在第 $s_j$ 天到第 $t_j$ 天（含两端）每天都占用 $d_j$ 个教室。

订单按输入顺序依次处理：处理第 $j$ 份订单时，若存在某一天剩余教室数小于 $d_j$，则处理停止，该订单无法满足。求第一个无法满足的订单编号；若全部订单都能满足，报告无订单失败。

样例：$n=4,\ m=3$，每天教室数为 $2,5,4,3$，三份订单依次为 $(2,1,3)$、$(3,2,4)$、$(4,2,4)$。第 1 份满足后剩余 $0,3,2,3$，第 2 份要求第 2~4 天每天 3 个，第 3 天只剩 2 个，故答案是订单 $2$。

正解

思路

朴素做法：完全按题意模拟。开一个数组 rem[] 记录每天剩余教室数，逐份处理订单，对每份订单把 $[s_j, t_j]$ 区间逐天减 $d_j$，一旦某天减完变成负数就立即停止并输出。单份订单最坏要扫 $O(n)$ 天，总复杂度 $O(nm)$，在 $n, m \leqslant 10^6$ 时约 $10^{12}$ 次操作，必然超时。瓶颈在于：每份订单都要真实地修改区间内的每一天。

观察一：失败位置具有单调性。 设 $f(k)$ 表示"前 $k$ 份订单能否全部满足"。如果前 $k$ 份能满足，那么前 $k-1$ 份是它的子集（每天占用的教室只会更少），也一定能满足。所以 $f$ 是一个先 true 后 false 的单调序列：

第一个为 false 的位置 $p+1$ 正是答案。单调性允许我们二分这个位置：在 $[0, m]$ 上二分最大的 $k$ 使 $f(k)$ 为 true，答案即 $k+1$；若 $k=m$ 则输出 $0$。二分次数为 $O(\log m)$。

观察二：判定可以差分。 $f(k)$ 只需要知道"前 $k$ 份订单叠加后，每一天的总需求是否超过当天供给"，并不需要真的逐单修改。对前 $k$ 份订单，每份只在差分数组上做两个点的修改：diff[s_j] += d_j、diff[t_j+1] -= d_j，再对 $n$ 天求一遍前缀和就得到每天的总需求 $\text{need}_i$，只要存在 $\text{need}_i > r_i$ 就返回 false。单次判定 $O(n+k)$。

两者结合：二分 $O(\log m)$ 次，每次判定 $O(n+m)$，总复杂度 $O((n+m)\log m)$，约 $2 \times 10^6 \times 20 = 4\times 10^7$ 次基本操作，轻松通过。

下面用样例展示二分判定的核心——差分叠加。判定 $f(2)$（前两份订单）时，差分数组与逐日前缀和如下（第 $i$ 列的"总需求"即第 1~$i$ 天订单的开头减去结尾的影响）：

看第 3 天这一列：订单 1（第 1~3 天每天 2 间）与订单 2（第 2~4 天每天 3 间）在第 3 天叠加，需求 $2+3=5$ 超过供给 $4$，所以 $f(2)=\text{false}$；而 $f(1)$ 显然为 true（见样例说明中剩余 $0,3,2,3$ 均非负）。二分在 $[0,3]$ 上收缩，最终得到最大可行 $k=1$，输出 $-1$ 和 $1+1=2$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m; vector<ll> r,d; vector<int> s,t;
bool ok_orders(int k){ vector<ll> diff(n+1); for(int j=0;j<k;j++){ diff[s[j]-1]+=d[j]; diff[t[j]]-=d[j]; } ll cur=0; for(int i=0;i<n;i++){cur+=diff[i]; if(cur>r[i]) return false;} return true; }
int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); if(!(cin>>n>>m)) return 0; r.resize(n); for(int i=0;i<n;i++) cin>>r[i]; d.resize(m); s.resize(m); t.resize(m); for(int j=0;j<m;j++) cin>>d[j]>>s[j]>>t[j]; int lo=0,hi=m; while(lo<hi){int mid=(lo+hi+1)/2; if(ok_orders(mid)) lo=mid; else hi=mid-1;} cout << (lo==m?0:-1) << '\n'; if(lo!=m) cout << lo+1 << '\n'; return 0; }

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"""借教室（NOIP2012 提高组）：二分第一个无法满足的订单 + 差分数组 O((n+m)log m) 判定。"""
import sys

def main() -> None:
    data = sys.stdin.buffer.read().split()
    it = iter(map(int, data))
    n, m = next(it), next(it)
    r = [next(it) for _ in range(n)]  # 每天可租教室数
    d = [0] * m  # 订单 j 需要的教室数
    s = [0] * m  # 订单 j 的起始天
    t = [0] * m  # 订单 j 的结束天
    for j in range(m):
        d[j], s[j], t[j] = next(it), next(it), next(it)

    def ok(k: int) -> bool:
        """前 k 份订单是否都能满足：差分累计每天总需求，与 r 比较。"""
        diff = [0] * (n + 1)
        for j in range(k):
            diff[s[j] - 1] += d[j]
            diff[t[j]] -= d[j]
        cur = 0  # 当前天被占用的教室总数（前缀和）
        for i in range(n):
            cur += diff[i]
            if cur > r[i]:
                return False
        return True

    lo, hi = 0, m  # ok(lo)=True（空集必满足），ok(hi)=False 之外即答案位置
    # 二分最大的 k 使前 k 份订单全部满足；答案为 k+1，全部满足输出 0
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if ok(mid):
            lo = mid
        else:
            hi = mid - 1
    print(0 if lo == m else -1)
    if lo != m:
        print(lo + 1)

if __name__ == "__main__":
    main()

复杂度

• 时间：二分 $O(\log m)$ 轮，每轮差分修改 $O(m)$、前缀和扫描 $O(n)$，共 $O((n+m)\log m)$。
• 空间：差分数组与订单数组均为 $O(n + m)$。Python 实现下 $10^6$ 规模的列表内存约几十 MB，注意读取输入时用 sys.stdin.buffer.read() 一次性读入，避免逐行 IO 拖慢速度。

一个实现细节：$d_j$ 与 $r_i$ 都可达 $10^9$，$m$ 份订单叠加后单日需求可达 $10^{15}$，Python 的整数天然无溢出问题；若用 C++ 实现则需使用 long long。

总结

• 朴素模拟逐区间修改，复杂度 $O(nm)$ 不可接受；瓶颈是"每份订单都真实修改一天"。
• 关键观察是失败位置的单调性，把"第一个失败订单"转化为可二分的判定问题。
• 判定用差分：每份订单只改两个点，前缀和还原每日总需求，单次 $O(n+m)$。
• 总复杂度 $O((n+m)\log m)$，是处理"区间叠加 + 找第一个不合法前缀"的经典套路（二分答案 + 差分判定）。