AcWing 503. 借教室
原题链接
简单
作者:
y差c
,
2024-03-14 14:38:04
,
所有人可见
,
阅读 19
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e6+10;
int w[N],d[N],s[N],e[N];
LL b[N];
int n,m;
bool check(int mid)
{
memset(b,0,sizeof b);
for(int i=1;i<=mid;i++)
{
b[s[i]]+=d[i];
b[e[i]+1]-=d[i];//构建前缀和 构建前mid个
}
for(int i=1;i<=n;i++)
{
b[i]+=b[i-1];// i 表示当前教室 b[i]+b[i-1] 就是差分数组还原的过程,计算操作后的值
if(b[i]>w[i]) return false;//如果找到一个值大于w[i],则表示他们相减是负的,不满足条件,false
}
return true;
}
int main()
{
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]>>e[i];
int l=0,r=m;//二分找出最后一天没有出现负值的编号 最后+1,因为从0开始的
while(l<r)
{
int mid = l+r+1>>1;
if (check(mid)) l=mid;
else r=mid-1;
}
if(r==m) puts("0");
else
{
cout<<-1<<endl<<r+1<<endl;
}
return 0;
}