题目描述

难度分:$1400$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(2 \leq n \leq 2 \times 10^5)$和长为$n$的括号字符串$s$，但不一定合法。

你需要把$s$分成尽量少的子序列，使得这些子序列都是美丽的，也就是从左到右看是合法括号字符串，或者从右到左看是合法括号字符串。

如果无法做到，输出$-1$。

否则，先输出子序列的个数（记作$m$）。然后输出每个$s[i]$所在子序列的编号（设子序列的编号从$1$到$m$）。

输入样例

4
8
((())))(
4
(())
4
))((
3
(()

输出样例

2
2 2 2 1 2 2 2 1
1
1 1 1 1
1
1 1 1 1
-1

算法

贪心

感觉今天灵佬的题目翻译没洛谷好理解，“从右往左看也是个合法括号序列”这句话看了好久没理解。其实就是从左往右，要么左括号数量不少于右括号数量，要么右括号数量不少于左括号数量。

其实没什么思路，但看着好像组数不会超过$2$。由于要求美丽子序列尽可能少，那子序列肯定就越长越好：

1. 如果$s$的左右括号数量不通，就无解，打印$-1$；
2. 如果$s$是个合法的括号子序列，答案就是$1$，所有字符都被分配到第$1$组；
3. 否则最多只可能分成$2$组，那就先用括号匹配的思路，先贪心地匹配一个合法括号序列出来，分到第$1$组。然后检查剩下的字符能不能构成一个合法的括号序列，可以就分到第$2$组。

在括号匹配的过程中(和)可以当做)和(，所以需要枚举四种情况：

1. 第$1$组前缀左括号的数量始终不超过右括号数量，第$2$组前缀左括号的数量始终不超过右括号数量。
2. 第$1$组前缀右括号的数量始终不超过左括号数量，第$2$组前缀右括号的数量始终不超过左括号数量。
3. 第$1$组前缀左括号的数量始终不超过右括号数量，第$2$组前缀右括号的数量始终不超过左括号数量。
4. 第$1$组前缀右括号的数量始终不超过左括号数量，第$2$组前缀左括号的数量始终不超过右括号数量。

每种情况都能$O(n)$求解。

复杂度分析

时间复杂度

枚举了$4$种情况，对于每种情况都要用栈对$s$进行括号匹配，也只会进行有限几次的$s$串遍历。因此，算法整体的时间复杂度为$O(n)$。

空间复杂度

空间瓶颈就是在括号匹配时需要开辟栈空间，在最差情况下会入栈$n$个下标。因此，额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>

using namespace std;
const int N = 200010;
int T, n, res, ans[N], temp[N];
char s[N];

void solve(char a, char b) {
    for(int i = 1; i <= n; i++) {
        temp[i] = 0;
    }
    int cnt = 0, idx = 1;
    stack<int> stk;
    for(int r = 1; r <= n; r++) {
        if(s[r] == a) {
            stk.push(r);
        }else {
            if(!stk.empty()) {
                int l = stk.top();
                stk.pop();
                temp[l] = temp[r] = idx;
            }else {
                cnt++;
                continue;
            }
        }
    }
    if(cnt == 0 && stk.empty()) {
        memcpy(ans, temp, sizeof(temp));
        res = 1;
        return;
    }
    while(!stk.empty()) stk.pop();
    if(*max_element(temp + 1, temp + n + 1)) idx++;
    for(int r = 1; r <= n; r++) {
        if(temp[r] == 1) continue;
        if(s[r] == b) {
            stk.push(r);
        }else {
            if(!stk.empty()) {
                int l = stk.top();
                stk.pop();
                temp[l] = temp[r] = idx;
            }else {
                return;
            }
        }
    }
    if(stk.empty()) {
        int counter[3] = {0};
        for(int i = 1; i <= n; i++) {
            if(!temp[i]) return;
            counter[temp[i]]++;
        }
        int cnt = (counter[1] > 0? 1: 0) + (counter[2] > 0? 1: 0);
        if(cnt < res) {
            res = cnt;
            memcpy(ans, temp, sizeof(temp));
        }
    }
    return;
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        scanf("%s", s + 1);
        int l = 0, r = 0;
        for(int i = 1; i <= n; i++) {
            l += s[i] == '('? 1: 0;
            r += s[i] == ')'? 1: 0;
        }
        if(l != r) {
            puts("-1");
        }else {
            res = 3;
            solve('(', ')');
            if(res > 1) solve('(', '(');
            if(res > 1) solve(')', '(');
            if(res > 1) solve(')', ')');
            if(res == 3) {
                puts("-1");
            }else {
                printf("%d\n", res);
                for(int i = 1; i <= n; i++) {
                    printf("%d ", ans[i]);
                }
                puts("");
            }
        }
    }
    return 0;
}