NC16564 借教室

题意

有天借教室信息，其中第天学校可以借出个教室。
有份订单，每份订单由组成，表示租借者需要从第天到第天（闭区间）内每天向学校借个教室
只需要考虑每天教室的数量能否满足当天订单，按照订单先后顺序借出教室，找到第一个无法被完成的订单（第天到第天至少有一天学校可借出教室数量少于则订单无法被完成）

思路

感觉说的不是很清楚，建议配合下方代码食用

判断一个订单能否被完成很简单：
只需要判断从第天到第天学校每天需要向外借出的教室数量是否大于实际可向外借出的教室数量即可。

所以我们有一个最基本的枚举思路：
按照先来后到的原则，我们从第一个订单开始枚举，判断学校剩下的可用教室数量能否满足当前订单即可，遇到第一个不能被满足的订单时直接输出订单编号。
但这样枚举的话，有个订单我们就需要进行次判断，时间复杂度过大，所以我们可以考虑二分+检验的方法快速的找到第一天无法被满足的订单。

一个订单最多可以租借天的教室，如果我们直接根据每个订单租借的时间逐个修改剩余可用的教室数量同样会带来大量不必要的操作，所以可以用前缀和来优化一下

代码

#include <iostream>

using namespace std;

int n;  //天数
int m;  //订单数
int classrooms[1000005];    //记录第i天可用教室classrooms[i]
int rentRequest[1000005][3];    //租借订单
int usedClassroom[1000005] = {0}; //前缀和记录某天被借出的教室数量

/**
 * @brief 判断第requestNumber个订单能否被完成
 * @param requestNumber int
 * @return bool
 */
bool judge(int requestNumber) {
    //把前缀和清一下0
    for (int i = 0; i <= n + 1; ++i) {
        usedClassroom[i] = 0;
    }
    //前缀和记录某天借出的教室数量
    for (int i = 1; i <= requestNumber; ++i) {
        usedClassroom[rentRequest[i][1]] += rentRequest[i][0];
        usedClassroom[rentRequest[i][2] + 1] -= rentRequest[i][0];
    }
    //某天需要借出的教室数量
    int usedRooms = 0;
    for (int i = 1; i <= n; ++i) {
        usedRooms += usedClassroom[i];
        //如果这一天需要的教室数量大于可以借出的教室数量，返回false
        if (usedRooms > classrooms[i])return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= n; ++i) {
        cin >> classrooms[i];
    }

    for (int i = 1; i <= m; ++i) {
        cin >> rentRequest[i][0]; //租借的数量
        cin >> rentRequest[i][1]; //租借开始在第几天
        cin >> rentRequest[i][2]; //租借结束在第几天
    }

    //二分寻找最后能完成的订单
    int left = 1, right = m, mid;
    while (left <= right) {
        mid = (left + right) >> 1;
        if (judge(mid))left = mid + 1;
        else right = mid - 1;
    }
    //left>m说明所有订单都可以被完成
    //否则有订单不能被完成，最后一次遇到不能被完成的订单会让right=mid-1
    //所以输出right+1
    if (left > m) {
        cout << 0 << endl;
    } else {
        cout << -1 << endl;
        cout << right + 1 << endl;
    }
}