算法
(二分答案+差分) $O((n + m)\log m)$
- 二分答案的可行性:第 $i$ 个订单无法满足,$i$ 以后的订单一定无法满足,满足单调性
- 前缀和:$sum[i] = sum[i - 1] + a[i]$,$\displaystyle sum[r] - sum[l - 1] = \sum_{i = l}^r a[i]$
- 差分:可以看作是前缀和的逆操作
已知 $sum$ 数组时,可以很容易求得 $a$ 的任意区间和
反过来,在 $a$ 的任意一个位置改变值,都会影响往后的一段区间
$a[l] += k$,$\displaystyle a[r + 1] -= k$,则 $sum[l] \sim sum[r]$ 都会 $+k$
用差分的方式标记每个订单施加的教室数目影响,$sum[i]$ 表示第 $i$ 天一共需要借出多少教室。$sum[i]$ 太大时,说明此订单已经无法满足。
C++ 代码
#include <bits/stdc++.h>
using std::cin;
using std::cout;
const int N = 1000010;
int n, m;
int diff[N], need[N], rest[N];
int l[N], r[N], d[N];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> rest[i];
for (int i = 1; i <= m; ++i) cin >> d[i] >> l[i] >> r[i];
auto isok = [&](int x) {
std::memset(diff, 0, sizeof diff);
for (int i = 1; i <= x; ++i) {
diff[l[i]] += d[i];
diff[r[i] + 1] -= d[i];
}
for (int i = 1; i <= n; ++i) {
need[i] = need[i - 1] + diff[i]; // need[i]表示第i天一共借出的教室有多少
if (need[i] > rest[i]) return false;
}
return true;
};
// 判断前m个订单能否满足
if (isok(m)) {
cout << "0\n";
return 0;
}
int begin = 1, end = m;
while (begin < end) {
int mid = begin + end >> 1;
if (isok(mid)) begin = mid + 1;
else end = mid;
}
cout << "-1\n" << begin;
return 0;
}