python/TangDou/Topic/PrefixAndSuffix/P1083.cpp

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
#define int long long
#define endl "\n"

int n, m;             // 天数和订单的数量
int r[N];             // 第i天学校有r[i]个教室可借用
int d[N], s[N], t[N]; // 借的教室数目、从第s天借到t天

int b[N];                   // 差分数组
bool check(int mid) {       // 判断能不能通过前mid个订单
    memset(b, 0, sizeof b); // 每次判断都要先初始化差分数组
    int sum = 0;            // 记录需要借的教室数
    // ① 构建差分数组
    for (int i = 1; i <= mid; i++) { // 枚举范围内[1~mid]所有订单
        b[s[i]] += d[i];             // 第i个订单，因为只会对在s~l之间要借用教室的人产生影响，所以可以差分
        b[t[i] + 1] -= d[i];         // 差分,注意:是t[i]+1，因为要包含t[i]这个点
    }
    // ② 还原成原数组,sum=a[i],也就是第i天需要借的教室总数
    for (int i = 1; i <= n; i++) {    // 枚举每一天
        sum += b[i];                  // 因为b是差分数组，所以sum就是在第i天的借教室的总数
        if (sum > r[i]) return false; // 如果要借的教室多于空的教室,返回不可行
    }
    return true; // 返回可行
}
signed main() {
    cin >> n >> m;                                            // n:天数，m：订单数量
    for (int i = 1; i <= n; i++) cin >> r[i];                 // 第i天可以租借的教室数量
    for (int i = 1; i <= m; i++) cin >> d[i] >> s[i] >> t[i]; // 借多少个，从哪天借到哪天

    /*
    ① 整体检查，如果所有订单都能通过，则输出0
      先定性，再定量！
      我们先不思考二分不二分，先用check函数获取所有订单是不是可以通过，如果能通过，那二分个啥！
      如果不能过，再已知有问题订单的情况下，再去找出问题订单，这样思路是最清晰的！
      避免不管是否有问题订单，全都冗杂到一个二分检查办法中去，那样容易思路不清，造成丢分！
    */
    if (check(m)) {        // 如果全部满足
        cout << 0 << endl; // 输出0
        exit(0);           // 直接结束程序
    }
    /*
    ② 整体检查未通过，知道肯定有订单无法满足，此时，再想办法找出是哪个订单第一个出现不满足的情况
    难道要一个个订单检查吗？
    不断的增加订单，会使得差分数组变化，但我们只看差分数组是不能判断是否有问题发生的，需要把差分数组还原
    为原数组后，才能进行检查,每输入一个订单，就还原一下原数组，那样就太慢了。
    能不能少还原，还能判断准呢？
    答：可以的，因为这件事具有单调性！第x个订单加上后:
    (1)如果1~x都符合条件，那证明前面的x-1个订单都是OK的，
    (2)如果1~x不符合条件，那后续的追加更多订单后的检查也肯定会失败！
    所以，可以使用二分进行求解查找是哪个订单导致第一个失败情况出现。
    */
    int l = 1, r = m; // 二分左右区间
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid))  // 如果可行
            l = mid + 1; // 增多订单
        else             // 否则
            r = mid;     // 减少订单
    }

    if (l == r) cout << 0 << end;
    ;

    cout << "-1" << endl
         << l; // 输出-1和 第一个不符合条件的订单
}