题目分析

本题要求处理 $n$ 天的教室租借情况，按顺序处理 $m$ 个订单，判断是否所有订单都能满足，若不能则找出第一个无法满足的订单编号。

解题思路

问题抽象

• 有 $n$ 天，每天初始有 $r_i$ 个可用教室
• 按顺序处理 $m$ 个订单，每个订单 $(d_j, s_j, t_j)$ 表示从第 $s_j$ 天到第 $t_j$ 天每天需要 $d_j$ 个教室
• 需要找出第一个使得某天教室数量为负的订单

核心算法：二分答案 + 差分数组

二分答案思想：

• 在区间 $[0, m]$ 中二分查找第一个无法满足的订单编号
• 检查前 $k$ 个订单是否都能满足

差分数组技巧：

• 对于区间 $[s_j, t_j]$ 的减法操作，可以通过差分数组在 $O(1)$ 时间内完成
• 具体操作：$$\begin{aligned} q[s_j] & \leftarrow q[s_j] + d_j \\ q[t_j + 1] & \leftarrow q[t_j + 1] - d_j \end{aligned} $$
• 最后通过前缀和还原实际的教室使用量

代码解析

#include <cstdio>
using namespace std;

long long n, m, rr[1000001], d[1000001], s[1000001], t[1000001];
long long i, ans, q[1000002];

// 二分检查函数
void getans(long long l, long long r) {
    long long mid = (l + r + 1) / 2, i;
    
    // 清空差分数组
    for (i = 1; i <= n + 1; i++)
        q[i] = 0;
    
    // 应用前mid个订单到差分数组
    for (i = 1; i <= mid; i++) {
        q[s[i]] = q[s[i]] + d[i];
        q[t[i] + 1] = q[t[i] + 1] - d[i];
    }
    
    // 计算前缀和，得到每天实际使用的教室数
    for (i = 1; i <= n + 1; i++)
        q[i] = q[i - 1] + q[i];
    
    // 检查是否有某天使用的教室数超过可用教室数
    for (i = 1; i <= n; i++)
        if (q[i] > rr[i])
            break;
    
    // 二分终止条件
    if (l == r) {
        ans = l;
        return;
    }
    
    // 递归二分
    if (i <= n)  // 前mid个订单不满足
        getans(l, mid - 1);
    else         // 前mid个订单满足
        getans(mid, r);
}

int main() {
    scanf("%lld%lld", &n, &m);
    
    // 读入每天可用教室数
    for (i = 1; i <= n; i++)
        scanf("%lld", &rr[i]);
    
    // 读入订单信息
    for (i = 1; i <= m; i++)
        scanf("%lld%lld%lld", &d[i], &s[i], &t[i]);
    
    // 二分查找第一个无法满足的订单
    getans(0, m);
    
    // 输出结果
    if (ans == m)
        printf("0");      // 所有订单都满足
    else
        printf("-1\n%lld", ans + 1);  // 输出第一个无法满足的订单编号
    
    return 0;
}

算法流程

1. 输入处理：读取 $n$, $m$ 和每天的可用教室数 $r_i$，以及所有订单信息
2. 二分查找：在区间 $[0, m]$ 中查找第一个无法满足的订单
3. 检查函数：
   • 使用差分数组模拟前 $k$ 个订单的教室分配
   • 计算前缀和得到每天实际使用的教室数
   • 检查是否所有天的使用量都不超过可用量
4. 结果输出：
   • 如果所有订单满足，输出 $0$
   • 否则输出 $-1$ 和第一个无法满足的订单编号

复杂度分析

• 时间复杂度：$O((n + m) \log m)$
  • 每次检查需要 $O(n + m)$ 时间
  • 二分查找进行 $O(\log m)$ 次检查
• 空间复杂度：$O(n + m)$

样例验证

对于样例输入：

4 3
2 5 4 3
2 1 3
3 2 4
4 2 4

算法过程：

1. 检查前 $2$ 个订单时，第 $3$ 天教室不足（需要 $3$ 个，只有 $2$ 个）
2. 继续二分，最终确定第 $2$ 个订单无法满足
3. 输出：

-1
2

与题目描述一致。