洛谷P1083 借教室

url: https://www.luogu.com.cn/problem/P1083

tag:
差分，前缀和，二分

思路：因为要求第一个不满足要求的订单，所以可以想到用二分。二分查找的是不满足要求的情况。通过订单的编号来查找，因为题目中写道有一个不满足要求的订单，后面就会停止分配，这可以抽象成假如有一个订单不满足，后面的订单一定也不满足，而前面的订单或许会满足，这就给二分提供了二段性。求是否满足条件这一块用到了差分，因为有一个区间加一个数这个标志，我们可以先开一个数组表示假如可以借出教室时每天需要有的教室数。通过前缀和求出这个教室数，然后和每天读入的可以借出的教室数比较，如果大于这个可以借出的教室数则表示不满足要求，返回true（因为求的就是不满足要求的订单的最小值，也就是第一个不满足要求的订单。）最后遍历完都符合则返回false。细节方面，因为求前缀和，用到了加法，然后题目的数据范围比较大，所以为了防止超过int的范围，可以让前缀和数组，也就是差分数组的类型为long long.同时因为是开了long long,所以在求前缀和的过程中反复使用的b数组的初始化就需要变成sizeof(long long) * (n + 1) ,（这里下标从1开始，一共n天所有有n + 1个数）。在输出结果的时候还有一个细节，就是题目说会有完全符合的情况，输出0，这里可以在二分的时候多一个标志，假如一直没有出现check(mid) 返回true的情况就说明完全符合，就输出0，反之，假如有一次check(mid)是true的情况就让这个标志为true，之后输出就输出二分结果即可。

代码：

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e6 + 10;
int n, m;
long long a[N], b[N];
struct lend {
    int d, s, t;
} Lend[N];
bool check(int x)
{
    memset(b, 0, sizeof(long long) * (n + 1));
    for (int i = 1; i <= x; i ++)
    {
        b[Lend[i].s] += Lend[i].d;
        b[Lend[i].t + 1] -= Lend[i].d;
    }
    for (int i = 1; i <= n; i ++)
    {
        b[i] += b[i - 1];
        if (b[i] > a[i]) return true;
    }
    return false;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i <= m; i ++)
    {
        cin >> Lend[i].d >> Lend[i].s >> Lend[i].t;
    }
    int l = 1, r = m;
    bool res = false;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (check(mid))
        {
            res = true;
            r = mid;
        }
        else l = mid + 1;
    }
    if (!res) cout << 0 << endl;
    else cout << -1 << '\n' << l << endl;
    return 0;
}