[WOJ1318]和最大

题目链接：###

题目分析：###

首先我们要知道当这是一个线性的序列的时候应该怎么做：最大子序和

这里是线性的，就把数组复制两遍即可

好像有些细节要处理（也可能是我代码写丑了），具体的都在代码里，挺好理解的

代码：###

#include<bits/stdc++.h>

#define MAXN (100000+5)

using namespace std;

inline int read(){

	int cnt=0,f=1;char c;

	c=getchar();

	while(!isdigit(c)){

		if(c=='-')f=-f;

		c=getchar();

	}

	while(isdigit(c)){

		cnt=cnt*10+c-'0';

		c=getchar();

	}

	return cnt*f;

}

int n,k,t,l=1,r=1,ans=-(1<<21);

int ansl,ansr;

int a[2*MAXN],sum[2*MAXN],q[2*MAXN],pos[2*MAXN],f[2*MAXN];

int main(){

	t=read();

	while(t--){

		l=r=0;

		q[0]=0;pos[0]=0;

		ans=-(1<<30);

		n=read();k=read();

		for(register int i=1;i<=n;i++){

			a[i]=a[i+n]=read();sum[i]=sum[i+n]=0;if(a[i]>ans){ans=a[i];ansl=ansr=i;}

		}

		for(register int i=1;i<=2*n;i++)sum[i]=sum[i-1]+a[i];

		for(register int i=1;i<=2*n;i++){

			int u=sum[i];

			while(u<q[r]&&l<=r)r--;

			q[++r]=u;pos[r]=i;

			while((pos[l]<i-k||pos[l]<i-n)&&l<=r)l++;

			int v=q[l];

			if(l==r)continue;

			if(u-v>ans){

				ans=u-v;

				ansl=pos[l]+1;ansr=i;

				if(ansl>n)ansl-=n;

				if(ansr>n)ansr-=n;

			}

		}

		printf("%d %d %d\n",ans,ansl,ansr);

	}

	return 0;

}

巴特西

[WOJ1318]和最大

题目链接：###

题目分析：###

代码：###

最新文章

热门文章