# NOIP2012 提高组 借教室## 题目描述在大学期间经常需要租借教室。大到院系举办活动小到学习小组自习讨论都需要向学校申请借教室。教室的大小功能不同借教室人的身份不同借教室的手续也不一样。面对海量租借教室的信息我们自然希望编程解决这个问题。我们需要处理接下来 $n$ 天的借教室信息其中第 $i$ 天学校有 $r_i$ 个教室可供租借。共有 $m$ 份订单每份订单用三个正整数描述分别为 $d

这道题是一个模拟题，我们需要按照订单的顺序来分配教室，并判断是否能够满足订单的要求。

首先，我们需要定义一个变量 rooms 来表示每天可供租借的教室数量。初始时，rooms 的值为第一天可供租借的教室数量。

然后，我们遍历订单，对于每个订单，我们需要判断从开始日期到结束日期的教室数量是否足够。如果足够，我们就将相应的教室数量减去订单中需要租借的数量。如果不足，我们就输出 -1，并将当前订单的编号输出。同时，我们需要终止循环，不再处理后续的订单。

最后，如果所有订单都能够满足，我们输出 0。

下面是具体的实现代码：

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> rooms(n);
    for (int i = 0; i < n; i++) {
        cin >> rooms[i];
    }

    for (int j = 0; j < m; j++) {
        int d, s, t;
        cin >> d >> s >> t;

        for (int i = s - 1; i < t; i++) {
            if (rooms[i] < d) {
                cout << -1 << endl;
                cout << j + 1 << endl;
                return 0;
            }
            rooms[i] -= d;
        }
    }

    cout << 0 << endl;

    return 0;
}

时间复杂度分析：

• 对于每个订单，我们需要遍历从开始日期到结束日期的教室数量，时间复杂度为 $O(n)$。
• 因此，总的时间复杂度为 $O(nm)$，其中 $n$ 为天数，$m$ 为订单数量，可以在给定的数据范围内运行。

空间复杂度分析：

• 我们使用了一个大小为 $n$ 的数组来存储每天可供租借的教室数量，因此空间复杂度为 $O(n)$，可以在给定的数据范围内运行。