单调队列优化求助
  • 板块P1714 切蛋糕
  • 楼主Light_az
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/5/25 21:13
  • 上次更新2023/10/23 14:46:27
查看原帖
单调队列优化求助
654958
Light_az楼主2023/5/25 21:13
#include<bits/stdc++.h>
#define ll long long
#define F(i,j,n) for(ll i=j;i<=n;i++)
#define B(i,j,n) for(ll i=j;i>=n;i--)
using namespace std;
const int N=1e6+10,NN=1e4+10;
ll n,m,k,x,y,u,v,w,cnt=0,ans=0,t=0,l,r,len,T;
ll mini=INT_MAX,maxi=0,p=998244353;
string s1,s2;
ll a[N],sum[N],q[N];
int main(){
	cin>>n>>m;
	F(i,1,n) cin>>a[i],sum[i]=sum[i-1]+a[i];
	l=1,r=0;
	F(i,1,n){
		while(q[l]+m<i) l++;
		ans=max(ans,sum[i]-sum[q[l]]);
		while(l<=r&&sum[q[r]]>=sum[i]) r--;
		q[++r]=i;
	}
	cout<<ans;
	return 0;
}
#include<bits/stdc++.h>
#define ll long long
#define F(i,j,n) for(ll i=j;i<=n;i++)
using namespace std;
const int N=1e6+10,NN=1e4+10;
ll n,m,k,x,y,u,v,w,cnt=0,ans=0,t=0,l,r,len,T;
ll mini=INT_MAX,maxi=0,p=998244353;
string s1,s2;
ll a[N],sum[N],q[N];
int main(){
	cin>>n>>m;
	F(i,1,n) cin>>a[i],sum[i]=sum[i-1]+a[i];
	l=1,r=0;
	F(i,1,n){
		while(l<=r&&sum[q[r]]>=sum[i]) r--;
		q[++r]=i;
		while(q[l]+m<i) l++;
		ans=max(ans,sum[i]-sum[q[l]]);
	}
	cout<<ans;
	return 0;
}

以下代码更改了单调队列顺序,有一个测试点出错,求原因

2023/5/25 21:13
加载中...