求小于等于k长度的最大区间和

题意

给出一个序列，求长度小于等于k的最大区间和并输出起点和终点

1<=n<=100000

1<=k<=n

题解：先算出前缀和,利用单调队列的性质，在单调队列中存储sum[] 的下标，并保持队列中的前缀和是保持递增的。

类似题 hdu3415

#include<stdio.h>

#include<iostream>

using namespace std;

#define de(x) cout<<#x<<" = "<<x<<endl

const int N  = 100010;

const int inf = 100000010;

int que[N],sum[N];

int main()

{

	int n,k,a,i,ans,ans1,ans2;

	int front,tail;

	scanf("%d%d",&n,&k);

	sum[0]=0;

	for(i=1;i<=n;i++)

	{

		scanf("%d",&a);

		sum[i]=sum[i-1]+a;

	}

	front = 0;tail = 0;

	ans=-inf;

	for(i=1;i<=n;i++)

	{

		while(tail>front&&sum[i-1]<sum[que[tail-1]])

			tail--;

		que[tail++]=i-1;

		while(tail>front&&i-que[front]>k)

			front++;

		if(ans<sum[i]-sum[que[front]])

		{

			ans=sum[i]-sum[que[front]];

			ans1=que[front]+1;

			ans2=i;

		}

	}

	printf("%d %d %d",ans,ans1,ans2);

}

巴特西

求小于等于k长度的最大区间和

题意

最新文章

热门文章