棍子排列 详细题解

题目回顾

给定整数 $n$（$2 \le n \le 100$）和一个长度为 $n - 1$ 的字符串 $s$，由字符 < 和 > 组成。
需要构造一个排列 $a_1, a_2, \dots, a_n$（每个数恰好是 $1 \sim n$ 的排列），满足：

• 若 $s_i = \texttt{<}$，则 $a_{i+1}$ 必须小于前面所有元素，即 $a_{i+1} < \min(a_1, \dots, a_i)$。
• 若 $s_i = \texttt{>}$，则 $a_{i+1}$ 必须大于前面所有元素，即 $a_{i+1} > \max(a_1, \dots, a_i)$。

题目保证一定有解，输出任意合法排列。

核心观察

从最后一个位置 $a_n$ 开始逆向推导：

• 若 $s_{n-1} = \texttt{<}$，则 $a_n$ 必须比前面所有元素都小，因此只能是当前可选数字中最小的那个。
  在最终排列中，这个最小值只能是 $1$（如果还没被使用）。推广：在逆向构造过程中，我们总是在已选中一些数后，为当前位置选择一个“极值”（最小或最大）。
• 若 $s_{n-1} = \texttt{>}$，则 $a_n$ 必须比前面所有元素都大，只能选当前可选数字中最大的那个，即 $n$。

我们移除已确定的 $a_n$，将问题规模减小到前 $n-1$ 个元素。此时前面元素的值域变为去掉已选数字后的集合。反复应用这个原则即可确定所有 $a_i$。

逆向构造算法

朴素做法

维护剩余可选数字集合 $b$，初始为 $\{1, 2, \dots, n\}$。
从 $i = n-1$ 递减到 $1$：

• 若 $s_i = \texttt{<}$，则 $a_{i+1} = \min(b)$，然后从 $b$ 中删除该值。
• 若 $s_i = \texttt{>}$，则 $a_{i+1} = \max(b)$，然后从 $b$ 中删除该值。

最后剩下的一个元素就是 $a_1$。
这样做的时间复杂度为 $O(n^2)$（每次找极值和删除需要 $O(n)$），对于 $n \le 100$ 已经足够，但可以优化到 $O(n)$。

优化：双指针维护剩余值域

由于初始集合是一段连续区间 $[1, n]$，每次删除极值后，剩余集合仍然是一段连续区间。
因此可以用两个指针 $l$ 和 $r$ 表示当前剩余值域 $[l, r]$：

• 删最小值 → l++
• 删最大值 → r--

具体步骤：

1. 初始化 $l = 1, r = n$。
2. 逆序遍历 $s$（下标 $i$ 从 $n-2$ 到 $0$）：
   • 若 $s[i] = \texttt{<}$，则 $a_{i+1} = l$，然后 $l \gets l+1$。
   • 若 $s[i] = \texttt{>}$，则 $a_{i+1} = r$，然后 $r \gets r-1$。
3. 循环结束后，$l$ 和 $r$ 相等，此时 $a_1 = l$。

该算法仅用 $O(n)$ 时间，且无需额外空间（除了存储排列的数组）。

正确性证明

引理：对于任意的 $i$（从后往前看），当我们处理到第 $i+1$ 个位置时，剩余未分配的数字一定是某一连续区间。
证明：初始为 $[1, n]$，每次移除的是当前区间的左端点或右端点，剩余区间显然仍连续。

引理：上述方法构造的排列满足题目条件。
证明：考虑第 $i+1$ 个位置的元素 $a_{i+1}$。

• 若 $s_i = \texttt{<}$，我们设定 $a_{i+1} = l$，即当前剩余数的最小值。由于前缀 $a_1, \dots, a_i$ 只会在后续步骤中使用大于 $l$ 的数字（因为 $l$ 已被移除），因此前缀所有元素都 $\ge l+1 > l = a_{i+1}$，满足小于前缀的条件。
• 若 $s_i = \texttt{>}$，我们设定 $a_{i+1} = r$（当前最大值），前缀元素将全部来自 $[l, r-1]$，因此均小于 $a_{i+1}$，满足大于前缀的条件。
  根据数学归纳法，最终排列合法。

示例运行

以 $n=5, s = \texttt{<<><}$ 为例：

• 初始 $l=1, r=5$，逆序处理 $s$ 的字符 >, <, <, <? 注意字符串 $s$ 长度 4：索引 3,2,1,0（从 0 开始）。
  具体：$s_4 = \texttt{<}$, $s_3 = \texttt{>}$, $s_2 = \texttt{<}$, $s_1 = \texttt{<}$。
  从 $i=3$ 递减到 $0$。

  1. $i=3$, $s_3 = \texttt{<}$ → $a_4 = l = 1$, $l=2$
  2. $i=2$, $s_2 = \texttt{<}$ → $a_3 = l = 2$, $l=3$
  3. $i=1$, $s_1 = \texttt{>}$ → $a_2 = r = 5$, $r=4$
  4. $i=0$, $s_0 = \texttt{<}$ → $a_1 = l = 3$, $l=4$ （此时循环结束，实际 $a_1$ 等于最后剩下的 $l$，但这里我们在循环中已经设置了 $a_1$？注意标准程序循环到 $i=0$，并将 $a[0]$ 最后赋值为 $l$。这里我们演示：循环结束后 $l=4, r=4$，$a_0 = l = 4$。但我们分配的顺序：$a_4$ 先被设置，最后 $a_0$。同时我们实际得到的序列是 $a = [?, ?, ?, ?, ?]$。按上述：$a_4 = 1, a_3 = 2, a_2 = 5, a_1 = 3$ 但还需要 $a_0$。若按循环 $i=0$ 时设置 $a_1$，最后 $a_0 = l$。这样得到 $a = [4, 3, 5, 2, 1]$。让我们检查：$s_1=\texttt{<}$ 要求 $a_2 < a_1$？但 $3 < 4$ 满足；$s_2=\texttt{<}$ 要求 $a_3 < a_1,a_2$ 即 $2 < 4,3$ 满足；$s_3=\texttt{>}$ 要求 $a_4 > a_1,a_2,a_3$ 即 $5 > 4,3,2$ 满足；$s_4=\texttt{<}$ 要求 $a_5 < a_1..a_4$ 即 $1 < 4,3,5,2$ 满足。得到排列 $[4,3,2,5,1]$？我们结果是 $[4,3,5,2,1]$。有些偏差因为对索引的理解。正确解释：标准代码中循环 for (int i = n - 2; i >= 0; i--) 设置的是 a[i + 1]。因此当 $n=5$ 时，$i$ 从 3 到 0，依次设置 $a_4, a_3, a_2, a_1$。按照例子 $s = \texttt{<<><}$，即 $s_0=\texttt{<}, s_1=\texttt{<}, s_2=\texttt{>}, s_3=\texttt{<}$。逆序：$i=3 \texttt{<} \to a_4 = l = 1; i=2 \texttt{>} \to a_3 = r = 5; i=1 \texttt{<} \to a_2 = l = 2; i=0 \texttt{<} \to a_1 = l = 3$。最后 $a_0 = 4$。得到 $[4,3,2,5,1]$，正是样例输出。完美。</li> </ol> </li> </ul>

     代码实现详解

     #include <bits/stdc++.h>
     using namespace std;
     
     void test() {
         int n;
         cin >> n;
         string s;
         cin >> s;
     
         int l = 1;
         int r = n;
         vector<int> a(n);
         for (int i = n - 2; i >= 0; i--) {
             if (s[i] == '<') {
                 a[i + 1] = l;
                 l++;
             }
             if (s[i] == '>') {
                 a[i + 1] = r;
                 r--;
             }
         }
         a[0] = l;
     
         for (int i = 0; i < n; i++) {
             cout << a[i] << " ";
         }
         cout << '\n';
     }
     
     int main() {
         ios_base::sync_with_stdio(false);
         cin.tie(nullptr);
     
         int t;
         cin >> t;
         for (int i = 0; i < t; i++) {
             test();
         }
         
         return 0;
     }```