NKOJ 3768 数列操作（单调队列/栈+DP）

发表于 |
字数统计: 663字 | 阅读时长 ≈ 3min

P3768数列操作

问题描述

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

输入格式

第一行两个正整数N (N <= 300,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

考虑一段满足条件的区间$[L+1,R]$，那么一定有$(R-L)*k<=Sum[R]-Sum[L]$。
为了方便讨论，我们把序列中每个数都减去k，那么有$0<=Sum[R]-Sum[L]$即$Sum[R]>=Sum[L]$
然后我们考虑以i为右端点的区间，那么需要找到满足$Sum[j]<=Sum[i]$的最小的j，鉴于时间复杂度的要求，我们考虑维护单调性。

假设$Sum[i]>=Sum[i-1]$，那么讨论$Sum[i]$肯定是更优的。
假设$Sum[i]<Sum[i-1]$，那么小于$Sum[i]$的也一定小于$Sum[i-1]$

因此我们先预处理从左往右维护一个单调递减的队列/栈，然后从右往左讨论，将小于$Sum[i]$的全部出队，这样就能找到第一个小于$Sum[i]$的数，并且对于$Sum[i-1]$的讨论不会产生影响，因为第一个小于$Sum[i]$的数也小于$Sum[i-1]$，否则$i-1$就不需要讨论。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<stdio.h>
#include<iostream>
#include<algorithm>
#define max(a,b) ((a>b)?(a):(b))
#define N 333333
using namespace std;
long long n,m,A[N],S[N];
long long Q[N],top,ans;
int main()
{
	int i,j,k;
	scanf("%lld%lld",&n,&m);
	for(i=1;i<=n;i++)scanf("%lld",&A[i]);
	while(m--)
	{
		scanf("%lld",&k);
		top=0;Q[++top]=0;
		for(i=1;i<=n;i++)
		{
			S[i]=S[i-1]+A[i]-k;
			if(S[i]<S[Q[top]])Q[++top]=i;
		}
		ans=0;
		for(i=n;i>=0;i--)
		{
			while(top>0&&S[i]>=S[Q[top]])top--;
			ans=max(ans,i-Q[top+1]);
		}
		printf("%lld ",ans);
	}
}