分析
我们要查询区间最值而且区间长度是固定的
这是我们才能用单调队列优化
代码
1 #include<iostream> 2 #include<queue> 3 #include<cstdio> 4 using namespace std; 5 int a[2000001],f[2000010],num[2000010],q[2000010]; 6 int main () 7 { 8 int n,k; 9 cin>>n>>k; 10 for (int i=1;i<=n;i++) 11 scanf("%d",&a[i]); 12 int head=1,tail=0; 13 for (int i=1;i<=n-1;i++) 14 { 15 while (num[head]<i-k+1&&head<=tail) head++; 16 while (a[i]<=q[tail]&&head<=tail) tail--; 17 num[++tail]=i; q[tail]=a[i]; 18 f[i]=q[head]; 19 } 20 cout<<0<<endl; 21 for (int i=1;i<=n-1;i++) 22 printf("%d ",f[i]); 23 }
分析
我们要求一个数列中连续m项的最大值
首先显然是要求一个前缀和
然后我们需要用一个单调队列来维护我s[i-1...k] 的最小值
1 #include<iostream> 2 #include<queue> 3 #include<cstdio> 4 using namespace std; 5 int a[2000001],f[2000010],num[2000010],q[2000010],s[2000010]; 6 int main () 7 { 8 int n,k; 9 cin>>n>>k; 10 for (int i=1;i<=n;i++) 11 scanf("%d",&a[i]),s[i]=s[i-1]+a[i]; 12 int ans=-1e9; 13 int head=1,tail=1; q[tail]=0; num[tail]=0; 14 for (int i=1;i<=n;i++) 15 { 16 while (num[head]<i-k&&head<=tail) head++; 17 ans=max(ans,s[i]-q[head]); 18 while (s[i]<=q[tail]&&head<=tail) tail--; 19 num[++tail]=i; q[tail]=s[i]; 20 } 21 cout<<ans; 22 }