AcWing 503. 借教室
原题链接
简单
作者:
CodeGamer
,
2024-04-03 20:42:42
,
所有人可见
,
阅读 1
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1000010;
int n, m;
int w[N];
int l[N], r[N], d[N];
LL b[N];
bool check(int mid)
{
memset(b, 0, sizeof b);
for (int i = 1; i <= mid; i ++ )
{ // 差分
// 在 l 处 + d,r + 1 处 - d
// 求 [l, r] 的前缀和,效果等同于在
// [l, r] 之间的每个数上加了一个 d
b[l[i]] += d[i];
b[r[i] + 1] -= d[i];
}
for (int i = 1; i <= n; i ++ )
{
b[i] += b[i - 1];
if (b[i] > w[i]) return false; // 订单 mid 不能被完成
}
return true;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
scanf("%d", &w[i]);
for (int i = 1; i <= m; i ++ )
scanf("%d%d%d", &d[i], &l[i], &r[i]);
int l = 0, r = m;
// 二分查找最后一个能被完成的订单
// l r最后会指向最大的满足条件的订单数,如果从1开始,
// 那么第一个订单满足或没订单满足都会指向1,需要特判
// 才可解决,为了避免这种麻烦,从零开始
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid; // 订单号 mid 可以被完成
else r = mid - 1; // 订单 mid 不能被完成
}
if (r == m) puts("0");
else printf("-1\n%d\n", r + 1);
return 0;
}