ac与72的区别没看懂
查看原帖
ac与72的区别没看懂
807042
lovely_aris楼主2024/8/2 20:25

这是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的位置 但没搞懂原理区别是什么

2024/8/2 20:25
加载中...