0%

「LOJ 2430」「POI2014」沙拉餐厅 Salad Baralad Bar

LOJ #2430

题意

一排$n$个水果$a_1..a_n$,分别是苹果$(j)$和橘子$(p)$,求最长的区间满足从左向右和从右向左取水果,任意时刻都有橘子数$\ge$苹果数,输出最长的区间长度

$n\le 10^6$


分析

记$d_i=\sum_{x=1}^i[a_x=p]-\sum_{x=1}^i[a_x=j]$

一个区间$[l,r]$满足条件当且仅当$\forall l\le i\le r,d_l\le d_i\le d_r$

可以用单调栈处理出最近的$l$满足$d_l>d_i$,于是以$i$为右端点的区间,最小的合法左端点是$[l+1,i]$中的最小值(如果存在)。

这个区间最小值位置可以在单调栈里顺便维护一下

复杂度 $\mathcal O(n)$


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<cstdio>
#include<algorithm>
const int N = 1000005;
int n, top, ans, stk[N], a[N], f[N];
char s[N];
int main() {
scanf("%d%s", &n, s+1);
for(int i=1; i<=n; ++i){
a[i]=a[i-1]+(s[i]=='j'?-1:1);
while(top && stk[top]<=a[i]) (a[f[top-1]]>a[f[top]]?f[top-1]=f[top]:0), --top;
if(a[f[top]]<=a[i]) ans=std::max(ans, i-f[top]);
++top, stk[top]=a[i], f[top]=i;
}
return printf("%d", ans), 0;
}