「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;
}