比較裸的單調隊列

先求前綴和，枚舉所有結束位置1~n+k即可

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 200005 using namespace std;int ans,a[maxn],sum[maxn];int main(){int T,N,K;scanf("%d",&T);while(T--){memset(sum,0,sizeof sum);scanf("%d%d",&N,&K);for(int i=1;i<=N;i++){scanf("%d",&a[i]);sum[i]=sum[i-1]+a[i];}for(int i=N+1;i<=N+1+K;i++){a[i]=a[i-N];sum[i]+=sum[i-1]+a[i];}ans=-1000000000;int ansl,ansr,l=1,r=1,q[maxn];//單調隊列求長度為k的區間中的最小值 q[1]=0;sum[0]=0;for(int i=1;i<=N+K;i++){while(l<=r && q[l]<i-K)l++;if(ans<sum[i]-sum[q[l]]){ans=sum[i]-sum[q[l]];ansl=q[l]+1,ansr=i>N?i-N:i;}while(l<=r && sum[q[r]]>=sum[i]) r--;q[++r]=i; }printf("%d %d %d\n",ans,ansl,ansr);}return 0; }

?

轉載于:https://www.cnblogs.com/zsben991126/p/10195384.html

總結

以上是生活随笔為你收集整理的hdu3415 单调队列模板题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。