借教室问题解析：二分法与差分前缀和的巧妙结合

题目P1083 [NOIP 2012 提高组] 借教室

https://www.luogu.com.cn/problem/P1083

题目描述

在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。

面对海量租借教室的信息，我们自然希望编程解决这个问题。

我们需要处理接下来 $n$ 天的借教室信息，其中第 $i$ 天学校有 $r_i$ 个教室可供租借。共有 $m$ 份订单，每份订单用三个正整数描述，分别为 $d_j,s_j,t_j$，表示某租借者需要从第 $s_j$ 天到第 $t_j$ 天租借教室（包括第 $s_j$ 天和第 $t_j$ 天），每天需要租借 $d_j$ 个教室。

我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提供 $d_j$ 个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。

借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。这里的无法满足指从第 $s_j$ 天到第 $t_j$ 天中有至少一天剩余的教室数量不足 $d_j$ 个。

现在我们需要知道，是否会有订单无法完全满足。如果有，需要通知哪一个申请人修改订单。

输入格式

第一行包含两个正整数 $n,m$，表示天数和订单的数量。

第二行包含 $n$ 个正整数，其中第 $i$ 个数为 $r_i$，表示第 $i$ 天可用于租借的教室数量。

接下来有 $m$ 行，每行包含三个正整数 $d_j,s_j,t_j$，表示租借的数量，租借开始、结束分别在第几天。

每行相邻的两个数之间均用一个空格隔开。天数与订单均用从 $1$ 开始的整数编号。

输出格式

如果所有订单均可满足，则输出只有一行，包含一个整数 $0$。否则（订单无法完全满足）

输出两行，第一行输出一个负整数 $-1$，第二行输出需要修改订单的申请人编号。

解析

为什么用二分法？

  1. 问题特性：订单处理具有顺序性，前k个订单满足与否存在单调性。若前k个订单无法满足，则后续更大k的订单也必然无法满足。
  2. 快速定位：二分法能在O(logm)次判断内找到第一个不满足的订单。将问题转化为判断前k个订单是否全满足，从而将时间复杂度从O(mn)优化至O((m+n)logm)。

为什么用差分前缀和？

  1. 高效处理区间操作：每个订单对连续区间[s, t]的教室数量减去d。差分数组在O(1)时间完成区间修改：

    • b[s] -= d
    • b[t+1] += d

  2. 快速计算每日剩余：通过差分数组的前缀和计算各天的总变化量，结合初始教室数判断是否满足需求。计算前缀和的时间为O(n)，极大优化了暴力遍历区间的O(kn)操作。

    这里各天的总变化量计算很巧妙！！！先把每组数据的差分直接加起来算出差分和，然后计算前缀和得到各天的总变化量，在和原数据进行对比判断。

算法流程

  1. 二分框架：确定左右边界，不断二分中点k，检查前k个订单是否可行。
  2. Check函数：
    • 应用差分处理前k个订单的区间修改。
    • 计算前缀和得到每日总变化量，叠加初始教室数判断是否出现负数（即不满足）。
  3. 结果判定：根据二分结果输出首个不满足的订单编号或0（全满足）。

复杂度分析

  • 差分处理：每次Check需O(k)处理差分，O(n)计算前缀和。
  • 总复杂度：O((m + n)logm)，完美应对1e6数据规模。

总结

二分法高效缩小问题范围，差分前缀和快速处理区间操作，两者结合解决了大规模数据处理难题。这种思想在类似“首个不满足条件”问题中具有广泛应用价值。

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

LL n, m;
LL a[1000010], b[1000010], d[1000010];
LL s[1000010], t[1000010];

void insert(LL l, LL r, LL num) {
	b[l] += num;
	b[r + 1] -= num;
}

bool check(LL num) {
	memset(b, 0, sizeof(b));
	for (LL i = 1; i <= num; i++) { // 差分计算
		insert(s[i], t[i], -d[i]);
	}
	for (LL i = 1; i <= n; i++) { 
		b[i] += b[i - 1]; // 前缀和计算
		if (a[i] + b[i] < 0) return false; // 判断
	}
	return true;
}

int main() {
	cin >> n >> m;
	for (LL i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
	}
	for (LL i = 1; i <= m; i++) {
		scanf("%lld%lld%lld", &d[i], &s[i], &t[i]);
	}
	
	// 二分
	LL l = 0, r = m + 1;
	while (l + 1 < r) {
		LL mid = l + (r - l) / 2;
		if (check(mid))
			l = mid;
		else
			r = mid;
	}
	if (r <= m) cout << -1 << endl << r;
	else cout << 0;
	
	return 0;
}