题意：给出了一个长度为n的括号对，每次只能反转一个括号。求最多能反转几个位置的括号使得字符串满足括号匹配。
思路：
思维题目，首先我们很容易想到的一个思路就是 如果当前位置i的字符串是 ‘(‘ 那么如果它能反转的话，一定是前i-1个位置抵消后的‘(‘要比i+1后抵消后的‘)‘少1. 反之如果是‘)‘的话，那么后i+1抵消后的‘(‘要比前i-1抵消后的‘)‘少1。 （抵消即是()已经完成了一对括号的匹配）
如果这样写的话，那么轻松就可以被hack掉。 例如( ( ) ) ( ( 和 ) ) ( ) ( (。究其原因在于从前往后 ) 不能比 ( 多，从后往前（不能比）多。
#include <bits/stdc++.h> using namespace std; int n; char s[1000005]; int sl[1000005],sr[1000005]; int main(){ scanf("%d", &n); scanf("%s", s + 1); int Sum = 0; for(int i = 1; i <= n; i++){ if(s[i] == ‘(‘) Sum++; else Sum--; if(Sum < 0){ for(int j = i;j <= n; j++) sl[j] = -1; break; } else sl[i] = Sum; } Sum = 0; for(int i = n; i >= 1; i--){ if(s[i] == ‘)‘) Sum++; else Sum--; if(Sum < 0){ for(int j = i; j >= 1; j--) sr[j] = -1; break; } else sr[i] = Sum; } int ans = 0; for(int i = 1; i <= n; i++){ if(sl[i - 1] >= 0 && sr[i + 1] >= 0){ if(s[i] == ‘(‘ && sl[i - 1] == sr[i + 1] + 1) ans++; if(s[i] == ‘)‘ && sl[i - 1] + 1 == sr[i + 1]) ans++; } } printf("%d\n", ans); return 0; }
CF1095E Almost Regular Bracket Sequence
原文：https://www.cnblogs.com/LYFer233/p/12781579.html