题目描述
- 差分也更新区间,也很给力。(以前就只记得前缀和,完全没有差分的概念,一顿线段树,看的懵,结果是差分)
- 这里的二分很妙
样例
// 分析结果就是,要么是区间内教室不够,要么是时间冲突会导致最终不可行
// 难点是怎么解决区间查询?是要分块吗?---> 用二分
#include <iostream>
#include <cstdio>
using namespace std;
int n, m;
const int N = 1e6 + 10;
int r[N], b[N];
int d[N], s[N], t[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];
}
for (int i = 1; i <= n; i++) {
// 计算
b[i] += b[i - 1];
// 检查原有数据是否不足
if (b[i] < 0) return false;
}
return true;
}
int main()
{
// 果然是这个问题,超时问题应该如何解决?这个是区间修改,应该用树状数组或者线段树吧?
cin >> 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]);
// 到m为止,是否可以
if (check(m)) {
cout << 0 << endl;
return 0;
}
int l = 1, r = m;
while (l < r) {
int mid = (l + r) >> 1;
if (!check(mid)) r = mid;
else l = mid + 1;
}
cout << -1 << endl;
cout << r << endl;
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla