算法知识点：二分，差分

复杂度：

解题思路：

由于随着订单数量的增加，每天可用教室的数量一定单调下降。
因此我们可以二分出第一天出现负值的订单编号。

剩下的问题是如何快速求出经过若干订单后，每天所剩的教室数量。
每个订单的操作是 全部减去 。

因此我们可以用差分来加速处理过程。

时间复杂度分析：

总共二分 次，其中 是订单数量。每次二分后使用差分求出每天最终教室数量，计算量是 ，因此总时间复杂度是 。

C++ 代码： 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
 
typedef long long LL; const int N = 1000010;
 
int n, m;
int r[N], d[N], s[N], t[N];
LL b[N];
 
bool check(int k)
{
    for (int i = 1; i <= n; i++) b[i] = r[i];
 
    for (int i = 1; i <= k; i++)
    {
        b[s[i]] -= d[i];
        b[t[i] + 1] += d[i];
    }
 
    LL res = 0;
    for (int i = 1; i <= n; i++)
    {
        res += b[i];
        if (res < 0) return true;
    }
 
    return false;
}
 
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &r[i]);
    for (int i = n; i; i--) r[i] -= r[i - 1];
 
    for (int i = 1; i <= m; i++) scanf("%d%d%d", &d[i], &s[i], &t[i]);
 
    int l = 1, r = m;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
 
    if (check(r))
    {
        puts("-1");
        printf("%d\n", r);
    }
    else puts("0");
 
    return 0;
}


另外，牛客暑期NOIP真题班限时免费报名
报名链接：https://www.nowcoder.com/courses/cover/live/248
使用优惠券免费报名：DCYxdCJ