题目大意
给出$N$个正整数$a[]$，再给出一个正整数$k$，现在可以进行如下操作：每次选择一个大于$k$的正整数$a[i]$，将$a[i]$减去$1$，选择$a[i-1]$或$a[i+1]$中的一个加上$1$。经过一定次数的操作后，问最大能够选出多长的一个连续子序列，使得这个子序列的每个数都不小于$k$。
总共给出$M$次询问，每次询问给出的$k$不同，你需要分别回答。
题目分析
这是一道很神奇的题。
因为相邻的数$+1,-1$，不难想到对和的变化很小，故将所有数减去$k$做一个前缀和，转化为求和$\ge 0$的最长区间。
为什么这样是对的？因为和$\ge 0$的区间一定能够通过调整使得满足条件。
然后想办法处理和$\ge 0$的最长区间，不难想到可以通过二分在$O(n\log n)$的时间范围内求出解，但这道题显然要卡$\log$，因此必须在$O(n)$的时间内出解。
然后我就不知道怎么做了。
KEKE_046表示可以从$1\rightarrow n$维护一个$sum$单调递减的栈，再从$n\rightarrow 1$维护一个$sum$单调递增的栈 ，答案肯定在两个栈中出现，然后双指针维护一下即可。
然而在两个栈中有重复元素的情况下很难处理。
看了一下标解，标解只维护了一个从$1\rightarrow n$的单调栈，然后从$n\rightarrow1$更新答案。
如图，我们在满足题目条件的时候尽量的让栈顶变低（这样可以使得区间变得更长）。
当$sum[i-1]\ge sum[i]$时，继续让栈顶变低。
当$sum[i-1]\lt sum[i]$时，看似需要将栈顶变高，其实不需要，因为即使将栈顶变高，在$sum[i+\cdots]$时已经统计到它，且答案一定比它大，因此将栈顶变高是没有贡献的，因此维持栈顶不动即可。
代码
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<stack>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=1000005;
LL n,m,k,a[maxn],sum[maxn];
int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int();
for(int i=1; i<=m; i++) {
k=Get_Int();
stack<int>S;
S.push(0);
for(int j=1; j<=n; j++) {
sum[j]=sum[j-1]+a[j]-k;
if(sum[S.top()]>sum[j])S.push(j);
}
int last=0,ans=0;
for(int j=n; j>=1; j--) {
while(!S.empty()&&sum[S.top()]<=sum[j]) {
last=S.top();
S.pop();
}
ans=max(ans,j-last);
}
printf("%d ",ans);
}
return 0;
}
|
