AcWing 503. 借教室
原题链接
简单
作者:
frankZ
,
2024-03-27 18:15:12
,
所有人可见
,
阅读 1
两种角度思考二分
C++ 代码
枚举最后一个满足
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int w[N];
int d[N], s[N], t[N];
LL b[N];
int n, m;
bool check(int x) {
memset(b, 0, sizeof b);
for (int i = 1; i <= x; 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] > w[i]) return false;
}
return true;
}
int main(void) {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> w[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 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
if (check(l + 1)) cout << 0;
else cout << -1 << endl << l + 1;
}
枚举第一个不符合
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int w[N];
int d[N], s[N], t[N];
LL b[N];
int n, m;
bool check(int x) {
memset(b, 0, sizeof b);
for (int i = 1; i <= x; 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] > w[i]) return true;
}
return false;
}
int main(void) {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> w[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(r)) cout << 0;
else cout << -1 << endl << l;
}