[bzoj2086][Poi2010]Blocks_单调栈

Blocks bzoj-2086 Poi-2010

题目大意：题目链接。

注释：略。

想法：首先，不难发现，如果连续的一段数的平均值不小于输入的k的话，这段数是满足题意的。

所以，我们再次简化一下：将每个数都减去k，即求极大区间，使得区间和为正。

将所有数的前缀和自尾至头压进单调栈，然后左指针遍历1->n，右指针在单调栈上扫即可。

最后，附上丑陋的代码... ...

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 1000010

using namespace std;

typedef long long ll;

ll q[N],top,n,m;

ll a[N],sum[N];

inline char nc()

{

	static char *p1,*p2,buf[100000];

	return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;

}

ll read()

{

	ll x=0; char c=nc();

	while(!isdigit(c)) c=nc();

	while(isdigit(c)) x=(x<<3)+(x<<1)+c-'0',c=nc();

	return x;

}

void dispose(ll val)

{

	ll ans=0;

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

	{

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

	}

	top=0;

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

	{

		if(sum[q[top]]>sum[i]) q[++top]=i;

	}

	for(int i=n,j=top;i>=0;i--)

	{

		while(j&&sum[q[j-1]]<=sum[i]) j--;

		ans=max(ans,i-q[j]);

	}

	printf("%lld ",ans);

}

int main()

{

	n=read(),m=read();

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

	{

		a[i]=read();

	}

	ll x;

	for(int i=1;i<=m;i++)

	{

		x=read();

		dispose(x);

	}

	puts("");

	return 0;

}

小结：%%%xqz

巴特西

[bzoj2086][Poi2010]Blocks_单调栈_双指针

最新文章

热门文章