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