借教室（二分）

题解思路

本题要求按顺序处理教室租借订单，当某个订单无法满足时（即从第 $s_j$ 天到第 $t_j$ 天中至少有一天的剩余教室数量不足 $d_j$ 个），立即停止并输出该订单编号。如果所有订单均可满足，则输出 0。

优化策略

二分：
- 二分查找第一个无法满足的订单编号。假设前 $mid$ 个订单可以满足，则尝试更大的 $mid$ ；否则，尝试更小的 $mid$ 。
- 最终， $ans$ 记录最后一个满足的订单编号。若 $ans = m$ ，则所有订单满足；否则， $ans+1$ 是第一个不满足的订单。
差分数组验证：
- 对于前 $k$ 个订单，使用差分数组高效计算每天的总需求：
  - 初始化差分数组 $diff$ （大小 $n+3$ ，初始为 0）。
  - 对每个订单 $(d_j, s_j, t_j)$ ：
    - $diff[s_j] \gets diff[s_j] + d_j$
    - $diff[t_j + 1] \gets diff[t_j + 1] - d_j$ （若 $t_j+1 \leq n+1$ ）
  - 计算前缀和 $cur$ ，得到每天的总需求。若存在 $cur > r_i$ ，则前 $k$ 个订单不满足。
- 恢复差分数组：验证后恢复 $diff$ 为初始状态，避免影响后续验证。

复杂度分析

时间复杂度： $O((n + m) \log m)$
- 二分次数 $O(\log m)$ 。
- 每次验证 $O(n + k)$ （ $k$ 为当前订单数），最坏 $O(n + m)$ 。
空间复杂度： $O(n)$ ，用于存储差分数组和教室数量。

代码实现

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

const int MAXN = 1000010;
int n, m;
int r[MAXN];
int d[MAXN], s[MAXN], t[MAXN];
long long diff[MAXN * 2]; // 差分数组，开大避免越界

// 检查前x个订单是否满足
bool check(int x) {
    // 应用前x个订单的差分
    for (int i = 1; i <= x; i++) {
        diff[s[i]] += d[i];
        if (t[i] + 1 <= n + 1) {
            diff[t[i] + 1] -= d[i];
        }
    }

    long long cur = 0;
    bool valid = true;
    // 计算前缀和并检查每天需求
    for (int i = 1; i <= n; i++) {
        cur += diff[i];
        if (cur > r[i]) {
            valid = false;
            break;
        }
    }

    // 恢复差分数组
    for (int i = 1; i <= x; i++) {
        diff[s[i]] -= d[i];
        if (t[i] + 1 <= n + 1) {
            diff[t[i] + 1] += d[i];
        }
    }
    return valid;
}

int main() {
    memset(diff, 0, sizeof(diff));
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &r[i]);
    }
    for (int i = 1; i <= m; i++) {
        scanf("%d %d %d", &d[i], &s[i], &t[i]);
    }

    int left = 1, right = m;
    int ans = 0; // 最后一个满足的订单编号
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (check(mid)) {
            ans = mid; // 前mid个订单满足
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    if (ans == m) {
        printf("0\n");
    } else {
        printf("-1\n%d\n", ans + 1);
    }

    return 0;
}

。 二分查找：