首页 > 代码库 > qscoj#19D(单调队列)
qscoj#19D(单调队列)
题目链接:http://qscoj.cn/problem/130/
题意:中文题诶~
思路:直接用单调栈搞一下就好了
代码:
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int MAXN=1e6+10; 5 const int inf=1e9; 6 int sum[MAXN], q[MAXN]; 7 8 int main(void){ 9 int n, k; 10 while(scanf("%d%d", &n, &k)!=EOF){ 11 for(int i=1; i<=n; i++){ 12 int x; 13 scanf("%d", &x); 14 sum[i]=sum[i-1]+x; 15 } 16 sum[n+1]=-inf; 17 int ans=0, front=0, rear=0; 18 for(int i=1; i<=n+1; i++){ 19 ans=max(ans, sum[i]); 20 if((front==rear||sum[i]>sum[q[front]])){ 21 if(i-q[rear+1]+1<k){ 22 q[++front]=i; 23 }else{ 24 while(i-q[rear+1]+1>=k&&front>rear){ 25 rear++; 26 } 27 q[++front]=i; 28 } 29 }else if(sum[i]<sum[q[front]]){ 30 while(front>rear&&sum[i]<sum[q[front]]){ 31 ans=max(ans, sum[q[front]]-sum[q[rear+1]]); 32 front--; 33 } 34 while(i-q[rear+1]+1>=k&&front>rear){ 35 rear++; 36 } 37 q[++front]=i; 38 } 39 } 40 printf("%d\n", ans); 41 } 42 return 0; 43 }
qscoj#19D(单调队列)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。