二分+差分数组经典应用：NOIP2012借教室问题详解

一、问题背景

借教室是NOIP2012提高组的Day2T2，考察了二分查找与差分数组的结合应用。题目需要处理n天中m个订单的教室借用请求，找出第一个无法满足的订单编号。

二、算法核心

1. 二分查找：快速定位第一个导致失败的订单

2. 差分数组：高效处理区间增减操作

3. 可行性检查：验证前mid个订单是否都能被满足

三、完整代码解析

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 1e6 + 5;
int n, m;
int r[MAXN];        // 每天可用教室数
int d[MAXN];        // 每个订单需求量
int s[MAXN], t[MAXN]; // 订单起止日期
int diff[MAXN];     // 差分数组
int temp[MAXN];     // 临时数组

bool check(int mid) {
    memset(diff, 0, sizeof(diff));
    // 构建前mid个订单的差分数组
    for (int i = 1; i <= mid; ++i) {
        diff[s[i]] += d[i];
        diff[t[i] + 1] -= d[i];
    }
    // 计算每日实际使用量
    for (int i = 1; i <= n; ++i) {
        temp[i] = temp[i - 1] + diff[i];
        if (temp[i] > r[i]) return false; // 发现不满足
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> r[i];
    for (int i = 1; i <= m; ++i) cin >> d[i] >> s[i] >> t[i];
    
    // 二分查找第一个不满足的订单
    int left = 1, right = m, ans = 0;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (check(mid)) {
            left = mid + 1;
        } else {
            ans = mid;
            right = mid - 1;
        }
    }
    
    if (ans) cout << "-1\n" << ans << endl;
    else cout << "0" << endl;
    
    return 0;
}

四、关键算法解析

1. 差分数组原理：

• diff[i] = a[i] - a[i-1]

• 区间[l,r]加d转化为：diff[l]+=d, diff[r+1]-=d

• 通过前缀和还原原数组

2. 二分查找设计：

• 左边界left=1，右边界right=m

• 当check(mid)为真时说明前mid个订单都合法

• 找到第一个使check返回false的mid

3. 复杂度分析：

• 二分O(logm)

• 每次check O(n+m)

• 总复杂度O((n+m)logm)

五、常见优化点

1. 使用快速输入输出加速（ios::sync_with_stdio）

2. 差分数组大小设置为n+2避免越界

3. 临时数组复用节省空间

六、易错点提醒

1. 差分数组还原时需要累加前项

2. 二分查找边界条件的处理

3. 订单编号从1开始的实际意义处理

参考：2012提高组借教室