【题解】[LuoguP3503]「BZOJ2086」[POI2010] Blocks

题目描述

给出N个正整数a[1..N]，再给出一个正整数k，现在可以进行如下操作：每次选择一个大于k的正整数a[i]，将a[i]减去1，选择a[i-1]或a[i+1]中的一个加上1。经过一定次数的操作后，问最大能够选出多长的一个连续子序列，使得这个子序列的每个数都不小于k。
总共给出M次询问，每次询问给出的k不同，你需要分别回答。

输入输出格式

输入格式：
第一行两个正整数N (N <= 1,000,000)和M (M <= 50)。
第二行N个正整数，第i个正整数表示a[i] (a[i] <= 10^9)。
第三行M个正整数，第i个正整数表示第i次询问的k (k <= 10^9)。
输出格式：
共一行，输出M个正整数，第i个数表示第i次询问的答案。

输入输出样例

输入样例#1：

5 6

1 2 1 1 5

1 2 3 4 5 6

输出样例#1：

5 5 2 1 1 0

题解

题目中只是问最长的一段子序列的长度，并且没有限制操作多少次，所以我们能发现一个性质，当且仅当这个序列的平均数大于等于k时，这个序列为合法序列。所以我们可以将每一个数都减去k，再找出最长的子序列和大于零
即找一个满足的$sum[i]-sum[j]$的数对i,j
可以发现如果$i<j$且$sum[i]-sum[j]$的话，选i做左端点比选j做左端点是更优的。
那么这样的话，我们只需要把s中自左向右单减的一段拿出来就行了。
还可以发现，如果r自右向左的话，l是随着r单调的，那么只需要维护一个单调递减的栈，然后r向左移动的时候不断弹栈就行了。

#include<cstdio>

#include<string>

#include<cstring>

#include<iostream>

#include<algorithm>

#define N 1000005

#define re register int

#define LL long long

using namespace std;

inline int read(){

	int x=0,w=1;

	char ch=getchar();

	while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

	if(ch=='-') w=-1,ch=getchar();

	while(ch<='9'&&ch>='0') x=(x<<3)+(x<<1)+ch-48,ch=getchar();

	return x*w;

}

int n,m,ans;

LL k,a[N],b[N],sum[N];

int top,stack[N];

int main() {

	freopen("in.txt","r",stdin);

	freopen("out.txt","w",stdout);

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

    for (re i=1;i<=n;++i) a[i]=read();

    while (m--) {

        k=read();ans=top=0;

		memset(sum,0,sizeof(sum));

        for(re i=1;i<=n;++i) sum[i]=sum[i-1]+a[i]-k;

        for(re i=1;i<=n;++i) if(sum[stack[top]]>sum[i]) stack[++top]=i;

        for(re i=n;i>=1;--i) {

            while(top&&sum[i]-sum[stack[top-1]]>=0) --top;

            ans=max(ans,i-stack[top]);

        }

        printf("%d ",ans);

    }

}

巴特西

【题解】[LuoguP3503]「BZOJ2086」[POI2010] Blocks

题目描述

输入输出格式

输入输出样例

题解

最新文章

热门文章