首页 > 代码库 > noip2012——提高组——借教室
noip2012——提高组——借教室
这题的关键在于前缀和数组以及二分。
具体实现挺简单的。
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int read(){ int t=1,num=0; char c=getchar(); while(c>‘9‘||c<‘0‘){if(c==‘-‘)t=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){num=num*10+c-‘0‘;c=getchar();} return num*t; } const int maxn=1000010; int n,m,a[maxn],d[maxn],s[maxn],t[maxn],q[maxn]; bool find(int num){ memset(q,0,sizeof(q)); for(int i=1;i<=num;i++){ q[s[i]]-=d[i]; q[t[i]+1]+=d[i]; } for(int i=1;i<=n;i++){ q[i]+=q[i-1]; if(q[i]+a[i]<0)return 1; } return 0; } void erfen(int l,int r){ if(l>=r){ if(r==m)puts("0"); else{printf("-1\n%d",l);} return; } int mid=(l+r)/2; if(find(mid)) erfen(l,mid); else erfen(mid+1,r); } int main() { n=read();m=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=m;i++){d[i]=read();s[i]=read();t[i]=read();} erfen(1,m); return 0; }
本文由Yzyet编写,网址为www.cnblogs.com/Yzyet。非Yzyet同意,禁止转载,侵权者必究。
noip2012——提高组——借教室
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。