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次询问的答案。

样例

样例输入

5 6
1 2 1 1 5
1 2 3 4 5 6

样例输出

5 5 2 1 1 0

思路：求平均值大于等于k的最长子序列。

因为求的是区间的最大平均值，所以不能以单个数进出栈的情况来考虑。

所以我们将每个数减去k，用前缀和来维护，与0进行比较。

如果一段区间的平均值大于k，那么这段区间是合法的，即这段区间的前缀和大于0。

我们用一个单调递减栈来维护，先将小于0的压入栈中（一定不为答案）但区间外不一定，因此答案越靠后越好，所以我们倒序遍历。

当栈顶元素小于当前元素，即栈顶元素到当前元素和大于0，为一组解。弹出栈顶元素。

当栈顶元素大于当前元素，当前解不合法，栈中其他解也不合法。

最后求出下标差的最大值。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+50;
long long n,m,k,ans,ans1,ma;
long long a[N],sum[N];
stack<int> s;
void getmin(){
	for(int i=1;i<=n;i++){
	    sum[i]=sum[i-1]+a[i]-k;
		while(sum[s.top()]>sum[i]) s.push(i);
	}
	for(int i=n;i>=1;i--){
		while(!s.empty()&&sum[s.top()]<=sum[i]){
			ans1=s.top();
			s.pop();	
		}
		if(sum[ans1]<=sum[i])
		ans=max(ans,abs(i-ans1));
	}
    printf("%lld ",ans);
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		ma=max(ma,a[i]);
	}
	for(int i=1;i<=m;i++){
		scanf("%lld",&k);
		memset(sum,0,sizeof(sum));
		while(!s.empty()) s.pop();
		s.push(0);
		ans=0;
		if(k>ma){
			printf("0 ");
			continue;	
		}
		getmin();
	}
	return 0;
}

注意，需要开long long