AT_icpc2014spring_e Parentheses 题解

题意：

给定 \(n\) 个字符串 \(s_1,s_2,\cdots s_n\)，每个字符串由括号 ( 和 ) 组成。

请问是否可以排列这 \(n\) 个字符串，使得这些字符串拼接后是一个合法的字符串。

合法的字符串定义如下：

空字符串是合法的。

如果 \(A\) 和 \(B\) 是合法的，那么 \(A\) 和 \(B\) 拼接后也是合法的。

如果 \(A\) 是合法的，那么将 \(A\) 放在一对匹配的括号内得到的字符串也是合法的。

任何其他字符串都是不合法的。

例如，()() 和 (()) 是合法的，而 ()) 和 ((() 是不合法的。

输入格式：

输入的第一行包含一个整数 \(n~(1 \leq n \leq 100)\)，表示字符串的数量。

接下来 \(n\) 行，每行包含一个字符串 \(s_i~(1 \leq | s_i | \leq 100)\)。\(s_i\) 中的所有字符都是 ( 或 )。

输出格式：

如果可以组成一个合法的字符串，则输出一行 Yes，否则输出 No。

这道题虽然简单，但是坑还是蛮多的。

记 \(u_i\) 为字符串 \(i\) 的左括号数，\(v_i\) 为字符串 \(i\) 的右括号数。

考虑将 \(u_i > v_i\) 的串按 \(v_i\) 顺序排序，将 \(v_i \ge u_i\) 的串按 \(u_i\) 降序排序。

接着维护一个变量 \(S\) ，遍历上面两个数组，每次 \(S\gets S-v_i\) 然后 \(S\gets S + u_i\) 。

如果第一步操作后 \(S<0\) 则无解，操作结束后 \(S \ne 0\) 也无解。

时间复杂度 \(\mathcal{O}(n\log n)\) ，复杂度瓶颈是排序

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(233))

char s[N]; int cnt1, cnt2;
struct node { int x, y; } a[N], b[N];
void fail() { cout << "No" << '\n'; exit(0); }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> (s + 1); int u = 0, v = 0;
        for(int j = 1; s[j]; j++)
            if(s[j] == '(') ++u; else { u ? --u : ++v; }
        u > v ? a[++cnt1] = {u, v} : b[++cnt2] = {u, v};
    }
    sort(a + 1, a + 1 + cnt1, [](node a, node b) { return a.y < b.y; });
    sort(b + 1, b + 1 + cnt2, [](node a, node b) { return a.x > b.x; });
    int sum = 0;
    for(int i = 1; i <= cnt1; i++)
        if((sum -= a[i].y) < 0) fail(); else sum += a[i].x;
    for(int i = 1; i <= cnt2; i++)
        if((sum -= b[i].y) < 0) fail(); else sum += b[i].x;
    cout << (sum ? "No" : "Yes") << '\n';
    return 0;
}