题目描述

关系

内容

问题分析

最初思路

直接模拟，由于题目中给出，我们是按照订单顺序进行处理的，所以我们只需要从前到后进行遍历，在遍历的过程中度教室进行操作：

1. 范围减法；
2. 查询区间 ${\displaystyle [l,r]}$ 的最小值；

遍历教室复杂度为 ${\displaystyle O(n)\ast O({\log }_{2}n)}$。

综上如果能够使用线段树，就可以解决这个问题了。但是常数可能很大。

这道题也有可以二分的点，二分的判断函数为当前订单是否是非法的。然后取左边界。取法的时间复杂度为 ${\displaystyle O({\log }_{2}n)}$.

不过判断函数，还是需要用到差分数组，来在 ${\displaystyle O(1)}$ 的时间内做到范围减法。

不过这个方法有一个缺陷，就是如果使用差分但不影响到原数组？可能有不需要差分的解法。根据我的感觉，预处理可能是一种思路。

关键在于判断订单 i，是否能够借到教室。如果能够预处理出一个数组，这个数组 s 的含义为：

1. s 数组能够得到 ${\displaystyle [1\dots i-1]}$ 之间的区间最大值；

思路分析

线段树的解法可以做，但是时间复杂度可能会超限。

最好的解法是我想的第二种，二分+差分。

执行流程设计

总结

代码实现

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 1e6 + 10;
int n, m;
int w[N], d[N], s[N], t[N];
ll b[N];

bool check(int mid) {
    memset(b, 0, sizeof b);
    
    for (int i = 1; i <= mid; i++) {
        b[s[i]] += d[i];
        b[t[i] + 1] -= d[i];
    }
    
    ll s = 0;
    for (int i = 1; i <= n; i++) {
        s += b[i];
        if (s > w[i]) return false;
    }
    return true;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
    for (int i = 1; i <= m; i++) scanf("%d%d%d", &d[i], &s[i], &t[i]);
    
    int l = 1, r = m + 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (!check(mid)) r = mid;
        else l = mid + 1;
    }
    
    if (l == m + 1) puts("0");
    else {
        printf("-1\n%d\n", l);
    }
    return 0;
}