CF1685C

luogubot · 2022-05-31 22:04:11 · 题解

给定一个由 n 个 ( 与 n 个 ) 组成的括号串，求出最少翻转多少个区间可以使得整个括号串合法，并构造一组方案。1\leq n\leq 10^5。

令左括号为 +1，右括号为 -1，需要使得最终序列前缀和都非负。

结论：任意括号串只需要翻转不超过 2 个区间。

证明：令 a_i 表示把括号看成 +1,-1 后的 [1,i] 的前缀和，则找到 a_x 值最大的任意一个 x，翻转 [1,x],[x+1,2n] 必定合法。考虑翻转后的前缀和 b_j，在 j\leq x 时等于 a_x-a_{x-j}\ge 0；在 j>x 时等于 a_x+a_{2n}-a_{j'-1}，其中 j' 是 j 在翻转前的位置，由于 a_{2n}=0，所以 a_x-a_{j'-1}\ge 0。

不需要翻转的情况判一下就好了，问题转到了是否存在只翻转一个区间的方案。令 l,r 是最前和最后一个前缀和小于 0 的位置，那么最终翻转的区间 [L,R] 一定要满足 L\leq l,R>r，最终 [1,L),(R,2n] 的前缀和没有改变，考虑 i\in[L,R] 的新前缀和 b_i=a_{L-1}+a_{R}-a_{i'}，其中 i' 是 i 翻转前的位置，同样在 [L,R] 中。那么需要 a_{L-1}+a_{R}\ge a_i 对于 i\in[L,R] 恒成立，于是贪心地选择 L\leq l,R>r 且 a_{L-1},a_{R} 最大的 [L,R] 检验即可。

时间复杂度 O(n)。