首页 > 代码库 > Vijos P1782 借教室 ( 前缀和&&差分序列)
Vijos P1782 借教室 ( 前缀和&&差分序列)
题目链接:借教室
题意:给出n天得教室数目,m个借教室得单子,按顺序借教室,问哪个单子不满足并输出
分析:可以用线段树做,会T,常数比较大,选择用差分序列维护前缀和,二分答案即可
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 int ans,n,m,r[1001000],d[1001000],s[1001000],t[1001000],pre[1001000]; 7 //inline int read(){int x=0;char ch=getchar();while(!(ch>=‘0‘&&ch<=‘9‘)) ch=getchar();while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();};return x;} 8 9 int check(int x) 10 { 11 int sum=0; 12 memset(pre,0,sizeof(pre)); 13 for(int i=1;i<=x;i++) pre[s[i]]+=d[i],pre[t[i]+1]-=d[i]; 14 for(int i=1;i<=n;i++) 15 { 16 sum+=pre[i]; 17 if(sum>r[i]) return 0; 18 } 19 return 1; 20 } 21 22 int main() 23 { 24 scanf("%d %d",&n,&m); 25 ans=0; 26 for(int i=1;i<=n;++i) scanf("%d",r+i); 27 for(int i=1;i<=m;++i) {scanf("%d %d %d",d+i,s+i,t+i);} 28 int l=1,r=m; 29 while(l<r) 30 { 31 int mid=(l+r)>>1; 32 if(check(mid)==0) ans=mid,r=mid; 33 else l=mid+1; 34 } 35 if(ans) printf("-1\n%d\n",ans); 36 else puts("0"); 37 }
Vijos P1782 借教室 ( 前缀和&&差分序列)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。