1 条题解
-
2
租借者需要从第 天到第 天租借教室（包括第 天和第 天），每天需要租借 个教室
这句话应该可以看出差分的味道。相当于就是对一段连续的区间内的数字全部减去某一个固定的数值。
如果我们直接差分后，然后挨个枚举每一个人，显然是超时的。
这里也可以看出二分枚举订单数量 ，如果二分枚举的这个都满足了，那么前面的肯定也都是满足的。
所以如果它没有出现无法满足的情况，就是直接验证 个是否符合，如若不符合，就二分检查看哪一个订单导致的不满足。
输入 以后，先求出差分数组
check函数里，进行差分，对当前的 的所有订单做差分处理，然后求前缀和，就得到了每一个 ，如果有一天的 ，那显然不符合要求，就 缩短范围继续。#include <iostream> using namespace std; const int N = 1e6 + 5; int n, m, a[N], A[N], diff[N], b[N], d[N], s[N], t[N]; bool check(int x) { for (int i = 1; i <= n; i++) diff[i] = b[i], a[i] = A[i]; //这里主要每次我们要重新更新差分数组和原数组 //所以一开始在输入的时候用两个数组进行了记录 for (int i = 1; i <= x; i++) { diff[s[i]] -= d[i]; diff[t[i] + 1] += d[i]; //正常的差分操作 } for (int i = 1; i <= n; i++) { a[i] = a[i - 1] + diff[i]; //求前缀和 if (a[i] < 0) return false; } return true; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i]; A[i] = a[i]; diff[i] = a[i] - a[i - 1]; b[i] = diff[i]; } for (int i = 1; i <= m; i++) { cin >> d[i] >> s[i] >> t[i]; } if (check(m))//先验证是否全部满足 { cout << 0; return 0; } int l = 1, r = m, mid, ans; while (l <= r) { mid = (l + r) / 2; if (check(mid)) { l = mid + 1; } else { r = mid - 1; } } cout << -1 << "\n" << l; return 0; }-
wsy1998 @ 2023-9-11 0:25:21
你甚至可以使用线段树，那么这就是一个区间修改，区间最值的板子了。
#include <bits/stdc++.h> #define ll long long #define ls p << 1 #define rs p << 1 | 1 using namespace std; const int N = 1e6 + 5; int n, m, a[N]; struct segment_tree { int l, r; int minn, add; } t[N << 2]; void push_up(int p) { t[p].minn = min(t[ls].minn, t[rs].minn); } void build(int p, int l, int r) { t[p].l = l, t[p].r = r; if (l == r) { t[p].minn = a[l]; return ; } int mid = l + r >> 1; build(ls, l, mid), build(rs, mid + 1, r); push_up(p); } void push_down(int p) { if (t[p].add) { t[ls].minn += t[p].add, t[rs].minn += t[p].add; t[ls].add += t[p].add, t[rs].add += t[p].add; t[p].add = 0; } } void modify(int p, int l, int r, int k) { if (t[p].l >= l && t[p].r <= r) { t[p].minn += -k; t[p].add += -k; return ; } int mid = t[p].l + t[p].r >> 1; push_down(p); if (l <= mid) modify(ls, l, r, k); if (r > mid) modify(rs, l, r, k); push_up(p); } int query(int p, int l, int r) { if (t[p].l >= l && t[p].r <= r) { return t[p].minn; } int res = 1e9; int mid = t[p].l + t[p].r >> 1; push_down(p); if (l <= mid) res = min(res, query(ls, l, r)); if (r > mid) res = min(res, query(rs, l, r)); return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; build(1, 1, n); for (int i = 1; i <= m; i++) { int d, s, t; cin >> d >> s >> t; modify(1, s, t, d); if (query(1, s, t) < 0) { cout << "-1\n" << i << "\n"; return 0; } } cout << 0; return 0; }
-
wsy1998
LV 10
MOD
@ 2022-6-13 22:11:21
- 1