这是72分的代码
#include<bits/stdc++.h>
using namespace std;
int in(){
int ans=0,f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) ans=ans*10+c-'0';
return ans*f;
}
void out(int x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10) out(x/10);
putchar(x%10+'0');
}
int n,k,a[1000010],x,ans;
struct F{
int a,id;
}q[2000010];
int fr=1,ba=1;
int main(){
n=in(),k=in();
for(int i=1;i<=n;i++){
x=in();
a[i]=a[i-1]+x;
while(ba>=fr&&q[ba].a>a[i]) ba--;
while(ba>=fr&&i-q[fr].id+1>k) fr++;
q[++ba]={a[i],i};
ans=max(ans,a[i]-a[q[fr].id]);
}
cout<<ans;
return 0;
}
下面是ac代码
#include<bits/stdc++.h>
using namespace std;
int in(){
int ans=0,f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) ans=ans*10+c-'0';
return ans*f;
}
void out(int x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10) out(x/10);
putchar(x%10+'0');
}
int n,k,a[1000010],x,ans;
struct F{
int a,id;
}q[2000010];
int fr=1,ba=1;
int main(){
n=in(),k=in();
for(int i=1;i<=n;i++){
x=in();
a[i]=a[i-1]+x;
while(ba>=fr&&q[ba].a>a[i]) ba--;
ans=max(ans,a[i]-a[q[fr].id]);
while(ba>=fr&&i-q[fr].id+1>k) fr++;
q[++ba]={a[i],i};
}
cout<<ans;
return 0;
}
只是改变了取ans max的位置 但没搞懂原理区别是什么