1347: PIPI的序列问题Ⅰ

这道题目使用了单调队列，并且保证了队尾与队首总在m之间，这样队首永远都是队尾的前面m-1个元素中的最小值。单调队列存储的是前缀和数组的索引

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=300000+10;
int q[N];
ll sum[N];
ll ans=0;
int main(){int n,m,v;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&v);sum[i]=sum[i-1]+v;}int head=0,rear=0;for(int i=1;i<=n;i++){while(head<=rear&&sum[q[rear]]>sum[i]) rear--;q[++rear]=i;while(head<=rear&&q[rear]-q[head]>m) head++;ans = max(ans,sum[q[rear]]-sum[q[head]]);}printf("%lld\n",ans);
}