2 条题解
-
2
做法:差分+二分
#include<bits/stdc++.h> using namespace std; #define int long long int n,m,di[1000001],ne[1000001],re[1000001],r[1000001],l[1000001],d[1000001]; int check(int x){ memset(di,0,sizeof(di)); for(int i=1;i<=x;i++){ di[l[i]]+=d[i]; di[r[i]+1]-=d[i]; } for(int i=1;i<=n;i++){ ne[i]=ne[i-1]+di[i]; if(ne[i]>re[i])return 0; } return 1; } signed main(){ scanf("%lld%lld",&n,&m); for(int i=1;i<=n;i++){ if(i)scanf("%lld",&re[i]); } for(int i=1;i<=m;i++){ if(i)scanf("%lld%lld%lld",&d[i],&l[i],&r[i]); } if(check(m)){ printf("0"); return 0; } int le=1,ri=m; while(le<=ri){ int mid=(le+ri)/2; if(check(mid))le=mid+1; else ri=mid-1; } if(le)printf("-1\n%lld",le); return 0; }
-
1
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int n,m; int diff[1000011],need[1000011],rest[1000011],r[1000011],l[1000011],d[1000011]; bool isok(int x) { memset(diff,0,sizeof(diff)); for(int i=1;i<=x;i++) { diff[l[i]]+=d[i]; diff[r[i]+1]-=d[i]; } for(int i=1;i<=n;i++) { need[i]=need[i-1]+diff[i]; if(need[i]>rest[i])return 0; } return 1; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&rest[i]); for(int i=1;i<=m;i++)scanf("%d%d%d",&d[i],&l[i],&r[i]); int begin=1,end=m; if(isok(m)){cout<<"0";return 0;} while(begin<end) { int mid=(begin+end)/2; if(isok(mid))begin=mid+1; else end=mid; } cout<<"-1"<<endl<<begin; }
- 1
信息
- ID
- 84
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 3
- 标签
- 递交数
- 40
- 已通过
- 9
- 上传者