题解 | #【入门班】借教室#
【入门班】借教室
https://ac.nowcoder.com/acm/problem/16564
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=1e6+9;
int a[N],c[N];
struct dd{
int d,s,t;
}p[N];
bool ck(int x){//x为订单顺序
memset(c,0,sizeof(c));
for(int i=1;i<=x;i++)
c[p[i].s]+=p[i].d,c[p[i].t+1]-=p[i].d;
for(int i=1;i<=n;i++){
c[i]+=c[i-1];
if(c[i]>a[i])return 0;
}
return 1;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++)cin>>p[i].d>>p[i].s>>p[i].t;
int l=0,r=m+1;
while(l+1!=r){
int mid=(l+r)>>1;
if(ck(mid))l=mid;
else r=mid;
}
if(r>m)cout<<0;
else cout<<r;
return 0;
}
查看23道真题和解析
