题目理解

我们有一个长度为 $n$ 的排列 $p$，需要：

1. 给每个位置分配 ( 或 )，形成合法的括号序列
2. 洗牌后（按照排列 $p$ 重新排列），仍然形成合法的括号序列

算法思路分析

核心思想

代码使用了贪心策略：

• 在原始序列中构造括号
• 在洗牌后的序列中也要满足括号合法性

关键数据结构

• a[i]：输入排列，表示洗牌后第 $i$ 个位置是编号为 a[i] 的卡牌
• p[x]：编号为 $x$ 的卡牌在洗牌后的位置
• s[i]：原始序列中第 $i$ 个位置的括号
• t[i]：洗牌后序列中第 $i$ 个位置的括号

算法步骤

1. 初始化检查

   if (n & 1) {
       cout << "NIE";
       return 0;
   }
   

   如果 $n$ 是奇数，直接输出 NIE，因为合法的括号序列长度必须是偶数。

2. 固定首尾括号

   s[1] = '(', t[p[1]] = '(';
   

   • 原始序列第一个位置必须是 (
   • 洗牌后编号为 1 的卡牌所在位置也必须是 (

3. 贪心分配括号

   for (int i = 2; i < n; i += 2) {
       q.push({-p[i], i});
       q.push({-p[i + 1], i + 1});
       int u = q.top().second;
       q.pop();
       s[u] = '(', t[p[u]] = '(';
   }
   

   • 每次处理一对卡牌 $(i, i+1)$
   • 使用最大堆（通过负数实现最小堆）选择洗牌后位置更靠前的卡牌作为 (
   • 这样保证在洗牌后的序列中，( 尽可能出现在前面

4. 验证洗牌后的序列

   for (int i = 1; i <= n; ++i) {
       if (t[i] == '(') ++val;
       else --val;
       if (val < 0) {
           cout << "NIE";
           return 0;
       }
   }
   

   检查洗牌后的括号序列是否合法（任何时候左括号数量不少于右括号）

5. 输出结果

   for (int i = 1; i <= n; ++i) {
       cout << s[i];
   }
   

算法正确性分析

为什么这样贪心？

• 在洗牌后的序列中，我们需要确保前缀和中左括号始终不少于右括号
• 通过让洗牌后位置靠前的卡牌成为 (，可以尽早提供左括号
• 这样最大程度避免了出现右括号多于左括号的情况

时间复杂度

• 堆操作：$O(n \log n)$
• 总体复杂度：$O(n \log n)$，对于 $n \leq 10^6$ 是可接受的

算法标签

• 贪心：每次选择洗牌后位置最靠前的卡牌作为左括号
• 构造：构建满足两个条件的括号序列
• 括号序列：核心问题类型
• 堆：用于高效选择最小位置

示例验证

以样例1为例：

输入：n=6, p=[4,6,1,2,3,5]
输出：(())()

算法过程：

1. 固定 s[1]='(', t[p[1]]=t[3]='('
2. 处理卡牌对 (2,3)、(4,5)、(6,7)
3. 贪心选择洗牌后位置靠前的作为 '('
4. 最终得到原始序列 (())()，洗牌后序列 ()()()