题解 | #小红的排列构造②#

题目链接

小红的排列构造②

题目描述

小红定义一个仅由 '0' 和 '1' 两个字符构成的字符串 $s$ 与一个长度为 $n$ 的数组 $p$ 为匹配，当且仅当满足下列两点：

若 $s_i = \text{'1'}$ ，则数组 $p$ 的前 $i+1$ 项（即 $p[0 \dots i]$ ）恰好构成一个 $1$ 到 $i+1$ 的排列。
若 $s_i = \text{'0'}$ ，则数组 $p$ 的前 $i+1$ 项（即 $p[0 \dots i]$ ）无法构成一个 $1$ 到 $i+1$ 的排列。

现在小红给出了一个长度为 $n$ 的字符串 $s$ ，请你构造一个长度为 $n$ 的排列 $p$ 使得 $s$ 与 $p$ 匹配；如果不存在这样的排列，请输出 -1。

解题思路

这是一个构造性问题。我们需要根据字符串 $s$ 的要求，一步步构建出排列 $p$ 。

首先，我们分析题目给出的两个核心条件：

s[i] = '1'：这意味着集合 $\{p_0, p_1, \dots, p_i\}$ 必须等于集合 $\{1, 2, \dots, i+1\}$ 。
s[i] = '0'：这意味着集合 $\{p_0, p_1, \dots, p_i\}$ 不能等于集合 $\{1, 2, \dots, i+1\}$ 。

一个至关重要的约束来自排列 $p$ 本身的定义： $p$ 必须是 $1$ 到 $n$ 的一个排列。这意味着，当 $i=n-1$ 时，前 $n$ 项（即整个数组）必须包含且仅包含 $1$ 到 $n$ 的所有整数。这恰好满足了 $s_{n-1} = \text{'1'}$ 的条件。因此，如果给定的字符串 $s$ 最后一个字符 $s_{n-1}$ 是 '0'，那么构造一个满足条件的排列 $p$ 是不可能的，因为这与 $p$ 必须是 $1 \dots n$ 的排列相矛盾。所以，这是第一个无解的情况。

接下来，我们考虑如何构造。一个有效的策略是从左到右遍历字符串 $s$ ，并把问题分解成若干个独立的“块”。每当遇到一个 '1'，就意味着一个前缀的构成被确定下来，这可以视为一个块的结束。

具体来说，一个块由若干个（可能为零个）'0' 跟着一个 '1' 组成。例如，如果 $s = \text{"001011"}$ ，我们可以将其分解为三个块：

s[0...2] = "001"
s[3...4] = "01"
s[5...5] = "1"

对于第一个块 s[0...2]，它结束于 $i=2$ 。 $s_2 = \text{'1'}$ 的条件要求 $\{p_0, p_1, p_2\}$ 必须是 $\{1, 2, 3\}$ 。同时，块内的 '0' 提供了额外的约束：

$s_0 = \text{'0'} \Rightarrow \{p_0\} \neq \{1\}$
$s_1 = \text{'0'} \Rightarrow \{p_0, p_1\} \neq \{1, 2\}$

如何满足这些 '0' 的约束呢？一个简单的方法是把块内可用的最大数字放在最前面。对于块 s[0...2]，可用的数字是 $\{1, 2, 3\}$ ，对应的位置是 $p_0, p_1, p_2$ 。如果我们倒序赋值： $p_0=3, p_1=2, p_2=1$ 。

检查 $s_0 = \text{'0'}$ ：前缀为 $\{3\}$ ，不是 $\{1\}$ ，满足。
检查 $s_1 = \text{'0'}$ ：前缀为 $\{3, 2\}$ ，不是 $\{1, 2\}$ ，满足。
检查 $s_2 = \text{'1'}$ ：前缀为 $\{3, 2, 1\}$ ，是 $\{1, 2, 3\}$ 的排列，满足。

这个策略是通用的。对于一个结束于 $i$ ，开始于 $j$ 的块（即 $s_i = \text{'1'}$ 且 $s_{j \dots i-1}$ 都是 '0'），我们需要将数字 $\{j+1, \dots, i+1\}$ 填入位置 $p_j, \dots, p_i$ 。通过将这些数字降序填入，即 $p_j=i+1, p_{j+1}=i, \dots, p_i=j+1$ ，我们可以保证所有中间的 '0' 条件都得到满足，因为每个前缀都会提前包含一个比当前前缀范围要求大的数。

基于此，我们可以设计出如下算法：

检查 $s_{n-1}$ 是否为 '0'，如果是，则输出 -1。
维护一个待分配数字的列表 pending_numbers。
遍历 $i$ 从 $0$ 到 $n-1$ ： a. 将数字 $i+1$ 加入 pending_numbers。 b. 如果 $s_i = \text{'1'}$ ，说明一个块结束了。此时 pending_numbers 里的所有数字需要被分配。我们将 pending_numbers 中的数字逆序（从大到小）依次填入当前块对应的位置中。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <string>
#include <numeric>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    string s;
    cin >> s;

    if (s.back() == '0') {
        cout << -1 << endl;
        return 0;
    }

    vector<int> p(n);
    vector<int> pending_numbers;
    int current_block_start = 0;

    for (int i = 0; i < n; ++i) {
        pending_numbers.push_back(i + 1);
        if (s[i] == '1') {
            int current_pos = i;
            while (!pending_numbers.empty()) {
                p[current_pos--] = pending_numbers.front();
                pending_numbers.erase(pending_numbers.begin());
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        cout << p[i] << (i == n - 1 ? "" : " ");
    }
    cout << endl;

    return 0;
}

import java.util.Scanner;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();

        if (s.charAt(n - 1) == '0') {
            System.out.println(-1);
            return;
        }

        int[] p = new int[n];
        ArrayList<Integer> pendingNumbers = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            pendingNumbers.add(i + 1);
            if (s.charAt(i) == '1') {
                int currentPos = i;
                while (!pendingNumbers.isEmpty()) {
                    p[currentPos--] = pendingNumbers.remove(0);
                }
            }
        }

        for (int i = 0; i < n; i++) {
            System.out.print(p[i] + (i == n - 1 ? "" : " "));
        }
        System.out.println();
    }
}

def solve():
    n = int(input())
    s = input()

    if s[-1] == '0':
        print(-1)
        return

    p = [0] * n
    pending_numbers = []
    
    for i in range(n):
        pending_numbers.append(i + 1)
        if s[i] == '1':
            start_pos = i - len(pending_numbers) + 1
            # 将 pending_numbers 逆序填入 p[start_pos ... i]
            p[start_pos : i + 1] = pending_numbers[::-1]
            pending_numbers = []
            
    print(*p)

solve()

算法及复杂度

算法：贪心、构造
时间复杂度： $\mathcal{O}(n)$ 。虽然代码中对于 pending_numbers 的操作（如 vector::erase 或 ArrayList::remove(0)）在循环中可能看起来是平方级的，但每个数字 $1 \dots n$ 只会被加入和移出列表一次。因此，总的时间复杂度是线性的。Python版本使用切片赋值，整体也是线性的。
空间复杂度： $\mathcal{O}(n)$ ，用于存储结果数组 $p$ 和辅助列表 pending_numbers。