把前 k 份订单是否可满足做成差分检查函数，再二分第一份出问题的订单编号。
OJ: luogu
题目 ID: P1083
难度:普及+/提高
标签:二分差分前缀和思维python
日期: 2026-06-20 11:16
题意
未来有 n 天教室资源，第 i 天有 r_i 个教室可借。
有 m 份订单，按顺序处理。
每份订单 (d, s, t) 表示从第 s 天到第 t 天，每天都要借 d 个教室。
规则是先到先得：
- 如果某份订单可以满足，就把对应天数的教室扣掉
- 如果某份订单无法满足，就立刻停止，并输出这份订单编号
要求判断：
- 所有订单是否都能满足
- 如果不能，第一份出问题的是哪一份
思路
先看一个最直接的暴力：
cpp
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<long long> room_cnt;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
room_cnt.resize(n + 1);
for (int i = 1; i <= n; i++) {
cin >> room_cnt[i];
}
for (int i = 1; i <= m; i++) {
long long d;
int s, t;
cin >> d >> s >> t;
bool ok = true;
for (int day = s; day <= t; day++) {
if (room_cnt[day] < d) {
ok = false;
break;
}
}
if (!ok) {
cout << -1 << '\n';
cout << i << '\n';
return 0;
}
// 按题意真正扣掉这份订单占用的教室。
for (int day = s; day <= t; day++) {
room_cnt[day] -= d;
}
}
cout << 0 << '\n';
return 0;
}brute.cpp 按题目流程逐份订单模拟：
- 先检查这份订单覆盖的每一天是否都还有足够教室
- 如果可以，就逐天扣减
- 如果不行，就输出当前订单编号
这个思路最贴近题意，但时间复杂度太高。
第一步：把问题改写成“前 k 份订单是否可行”
如果我们固定一个 k，只问：
- 前
k份订单能不能全部满足？
这个判断是有单调性的：
- 如果前
k份可以满足，那么前1..k-1份一定也可以满足 - 如果前
k份不能满足，那么再往后加订单也不可能重新变可行
于是答案就是：
- 第一份使系统失效的订单编号
这就天然可以二分。
第二步：如何快速检查前 k 份订单
对于前 k 份订单，每份订单 (d, s, t) 都是在区间 [s, t] 上每天消耗 d 个教室。
这正是一个典型的区间加模型：
- 在
diff[s]加上d - 在
diff[t+1]减去d
最后做一次前缀和，就能得到每一天总共被借走多少教室。
如果某一天满足：
被借走的教室数 > r_i
那么前 k 份订单就不可行。
所以 check(k) 可以这样写：
- 清空差分数组
- 把前
k份订单全部打进差分 - 扫一遍前缀和，检查是否有某天超出容量
第三步：二分第一份失败订单
若 check(m) 成立，说明所有订单都能满足，输出 0。
否则二分最小的 k，满足：
check(k)为假
这个 k 就是第一份出问题的订单编号。
Python 知识
- 三个
array分别保存订单数量、起点和终点，比保存百万个 Python 元组更节省内存。 zip(rooms, difference)同步遍历每天容量和差分变化。- 自定义分块整数迭代器用于百万级数据；普通规模仍优先使用更短的
map(int, input().split())。
代码
python
import os
from array import array
def read_ints():
number = 0
reading = False
while chunk := os.read(0, 1 << 20):
for byte in chunk:
if 48 <= byte <= 57:
number = number * 10 + byte - 48
reading = True
elif reading:
yield number
number = 0
reading = False
if reading:
yield number
data = iter(read_ints())
n, m = next(data), next(data)
rooms = array("q", (next(data) for _ in range(n)))
amount = array("q", [0]) * m
start = array("i", [0]) * m
end = array("i", [0]) * m
for i in range(m):
amount[i], start[i], end[i] = next(data), next(data) - 1, next(data)
def feasible(count):
difference = array("q", [0]) * (n + 1)
for i in range(count):
difference[start[i]] += amount[i]
difference[end[i]] -= amount[i]
used = 0
for available, change in zip(rooms, difference):
used += change
if used > available:
return False
return True
if feasible(m):
print(0)
else:
left, right = 1, m
while left < right:
middle = (left + right) // 2
if feasible(middle):
left = middle + 1
else:
right = middle
print(-1, left, sep="\n")复杂度
- 每次
check(k)的复杂度是 - 二分一共调用
次 - 总复杂度可记为
总结
这题的关键是把原题拆成两层：
- 外层二分“第一份失败订单”
- 内层差分检查“前 k 份订单是否可行”
一旦看出“前 k 份是否可行”具有单调性，题目就自然转成了“二分答案 + 差分判定”。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
