算法:二分 + 差分
时间复杂度:$O(n \times log(m))$
该题二分的为第一个不满足订单的编号,二分可详见 AcWing 789. 数的范围。
其次该题的数据范围最大可达 $10^6$,$O(n^2)$ 的算法必定超时,所以在区间 $[l, r]$ 之间减去 $d_i$ 时,可采用差分具体详见 AcWing 797. 差分,可在 $O(1)$ 的时间内完成。
C++ 代码
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int n, m;
int r[N], d[N], s[N], t[N];
LL b[N];
bool check(int mid)
{
for (int i = 1; i <= n; ++i) b[i] = r[i] - r[i - 1];
for (int i = 1; i <= mid; ++i) {
b[s[i]] -= d[i];
b[t[i] + 1] += d[i];
} // 对 [1, mid] 区间的订单进行操作
for (int i = 1; i <= n; ++i) b[i] += b[i - 1]; // 前缀和恢复原订单
for (int i = 1; i <= n; ++i) {
if (b[i] < 0) {
return true;
}
}
return false;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> r[i];
for (int i = 1; i <= m; ++i) cin >> d[i] >> s[i] >> t[i];
int l = 0, r = m;
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
if (!check(m)) {
puts("0");
}
else {
cout << -1 << endl << r << endl;
}
return 0;
}
为什么前缀和恢复用r[i]就是错的呢
为啥l从0开始呀