小红的排列构造②

思路

题目给了一个长度为 的 01 字符串 ，要求构造一个 的排列 ，满足：

  • 如果 ，前 个元素恰好构成 的排列
  • 如果 ，前 个元素不构成 的排列

什么时候无解？

首先， 必须是 '1'。因为整个数组一定是 的排列，最后一个位置不可能不满足。如果 ，直接输出 。

除此之外，其实总能构造出合法排列。

怎么构造？

关键观察：前 个元素是 的排列，等价于这些元素的最大值恰好是 。

所以我们可以按 '1' 的位置把数组切成若干段。假设 '1' 出现在位置 （其中 ），那么每一段就是 ，对应要填入的值是 。

为了让段内除最后一个位置外的前缀都不是合法排列，我们只需要把该段最大的那个值（即 ）放到段的第一个位置，剩下的值按顺序填。这样一来，从段的第一个位置开始，前缀的最大值就已经"超标"了，直到段末尾刚好补齐，最大值恰好等于位置编号。

举个例子：，。'1' 出现在位置 2 和 4。

  • 第一段 ：填 （把 3 放最前面）
  • 第二段 ：填 （把 5 放最前面）
  • 最终排列：

验证一下：前缀最大值依次是 ，对应位置编号 。只有位置 3 和 5 处最大值等于编号，对应 中的 '1'。

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    char s[n+1];
    scanf("%s", s);

    if(s[n-1] != '1'){
        printf("-1\n");
        return 0;
    }

    vector<int> ans(n);
    int prev = -1;
    for(int i = 0; i < n; i++){
        if(s[i] == '1'){
            int start = prev + 1;
            ans[start] = i + 1;
            for(int j = start + 1; j <= i; j++){
                ans[j] = j;
            }
            prev = i;
        }
    }

    for(int i = 0; i < n; i++){
        printf("%d%c", ans[i], i==n-1?'\n':' ');
    }
    return 0;
}

import java.util.*;

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) != '1') {
            System.out.println(-1);
            return;
        }

        int[] ans = new int[n];
        int prev = -1;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '1') {
                int start = prev + 1;
                ans[start] = i + 1;
                for (int j = start + 1; j <= i; j++) {
                    ans[j] = j;
                }
                prev = i;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (i > 0) sb.append(' ');
            sb.append(ans[i]);
        }
        System.out.println(sb);
    }
}

import sys
input = sys.stdin.readline

n = int(input())
s = input().strip()

if s[n - 1] != '1':
    print(-1)
else:
    ans = [0] * n
    prev = -1
    for i in range(n):
        if s[i] == '1':
            start = prev + 1
            ans[start] = i + 1
            for j in range(start + 1, i + 1):
                ans[j] = j
            prev = i
    print(' '.join(map(str, ans)))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', (line) => lines.push(line.trim()));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const s = lines[1];

    if (s[n - 1] !== '1') {
        console.log(-1);
        return;
    }

    const ans = new Array(n).fill(0);
    let prev = -1;
    for (let i = 0; i < n; i++) {
        if (s[i] === '1') {
            const start = prev + 1;
            ans[start] = i + 1;
            for (let j = start + 1; j <= i; j++) {
                ans[j] = j;
            }
            prev = i;
        }
    }
    console.log(ans.join(' '));
});

复杂度

  • 时间复杂度：，每个位置只被访问一次。
  • 空间复杂度：，存储答案数组。