P1083 [NOIP2012 提高组] 借教室

题目链接：

本题由于是对某一段区间的数统一进行删除某个数的操作，很容易想到差分。

对于能否二分，有一个界定标准：状态的决策过程或者序列是否满足单调性或者可以局部舍弃性。在本题中，由于随着订单数量的增加，每天可用教室的数量一定单调下降。也即，如果前一份订单都不满足，那么之后的所有订单都不用继续考虑；而如果后一份订单都满足，那么之前的所有订单一定都可以满足，符合局部舍弃性，所以可以二分订单数量。

注：计算前缀和的时候最坏情况下是 \(10^6 \cdot 10^9=10^{15}\) 可能会爆 \(\rm int\)，因此差分数组要开 \(\rm long\) \(\rm long\)。

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int N = 1e6 + 5;

int n, m, r[N], d[N], s[N], t[N];
LL b[N];//差分数组

bool check(int x) {//二分出第一个不满足题意的数
    for (int i = 1; i <= n; i++) b[i] = r[i] - r[i - 1];//由于要
    for (int i = 1; i <= x; i++) {
        b[s[i]] -= d[i];
        b[t[i] + 1] += d[i];
    }//对[l,x]范围内的订单操作
    for (int i = 1; i <= n; i++) {
        b[i] += b[i - 1];//前缀和，恢复原数据
        if (b[i] < 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 = 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(m)) puts("0");//一直到最后一个订单全部都满足就输出0
    else printf("-1\n%d", l);//否则输出二分出的答案
    return 0;
}