如果您可以吊打我 勿喷！！！
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
//#include <windows.h>
#define ll long long
#define rg register
#define ull unsigned long long
using namespace std;
int n,m;
int k,tot,head=1,tail=0;
int a[2000009],q[2000009];
inline int read()
{
int x=0,f=1;
char ch;
while (ch < ‘0‘ || ch > ‘9‘) {if (ch==‘-‘)f = -1;ch = getchar();}
while (ch >= ‘0‘ && ch <= ‘9‘){x = x*10+ch-‘0‘;ch = getchar();}
return f*x;
}
int main()
{
n=read(),m=read();
for(rg int i=1;i<=n;i++)
a[i]=read();
for(rg int i=1;i<=n;i++)
{
printf("%d\n",a[q[head]]);
while(i-q[head]+1>m&&head<=tail)
head++;
while(a[i]<a[q[tail]]&&head<=tail)
tail--;
q[++tail]=i;
}
//system("pause");
return 0;
}
代码：
#include<bits/stdc++.h> using namespace std; #define re register int #define ll long long #define maxn 1000009 #define maxm inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=(x<<1)+(x<<3)+(ll)(ch-‘0‘);ch=getchar();} return x*f; } int q[maxn],a[maxn]; int n,m,k,ans,tot,head,tail; void Ask_MIN() { head=1,tail=0; for(int i=1;i<=n;i++) { while(head<=tail&&i-q[head]+1>m) head++; while(head<=tail&&a[q[tail]]>=a[i]) tail--; q[++tail]=i; if(i>=m) printf("%d ",a[q[head]]); } } void Ask_MAX() { head=1,tail=0; for(int i=1;i<=n;i++) { while(head<=tail&&i-q[head]+1>m) head++; while(head<=tail&&a[q[tail]]<=a[i]) tail--; q[++tail]=i; if(i>=m) printf("%d ",a[q[head]]); } } int main() { n=read(),m=read(); for(int i=1;i<=n;i++) a[i]=read(); Ask_MIN(); Ask_MAX(); return 0; }
代码：
#include<bits/stdc++.h> using namespace std; #define re register int #define ll long long #define maxn 1000009 #define maxm inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=(x<<1)+(x<<3)+(ll)(ch-‘0‘);ch=getchar();} return x*f; } int sum[maxn<<1],q[maxn<<1],a[maxn<<1]; int n,m,k,ans,tot,head,tail; int main() { n=read(); for(int i=1;i<=n;i++) a[i]=read(),a[i+n]=a[i]; for(int i=1;i<=2*n;i++) sum[i]=sum[i-1]+a[i]; head=1,tail=0; for(int i=1;i<=n*2-1;i++) { while(head<=tail&&i-q[head]+1>n) head++; while(head<=tail&&sum[i]<=sum[q[tail]]) tail--; q[++tail]=i; if(i>=n&&sum[q[head]]-sum[i-n]>=0) ans++; } printf("%d\n",ans); return 0; }
代码：
#include<bits/stdc++.h> using namespace std; #define re register int #define ll long long #define maxn 500009 #define maxm inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=(x<<1)+(x<<3)+(ll)(ch-‘0‘);ch=getchar();} return x*f; } int sum[maxn],q[maxn]; int n,m,k,ans,tot,mx,head,tail; int main() { n=read(),m=read(); for(int i=1;i<=n;i++) { int x=read(); sum[i]=sum[i-1]+x; } head=1,tail=0; for(int i=1;i<=n;i++) { while(head<=tail&&i-q[head]>m) head++; ans=max(ans,sum[i]-sum[q[head]]); while(head<=tail&&sum[q[tail]]>=sum[i]) tail--; q[++tail]=i; } printf("%d\n",ans); }
原文：https://www.cnblogs.com/_Yrh/p/10511917.html