题解 | 小红的排列构造②

n = int(input())
s=input().strip()
p = [i+1 for i in range(n)]
temp_index = 0
total_len = len(s)
for j in range(total_len):
    if s[j] == "1":
        p[j], p[temp_index] = p[temp_index], p[j]
        temp_index = j+1

if temp_index >= n:
    str_arr = [ str(i) for i in p]
    print(" ".join(str_arr))
else:
    print(-1)

这个解题思路为，将“0*1”这个正则形式作为一个段，即0-n个0后跟一个1，这段标明前面0的部分一定无法构成排列，当且仅当1的位置可以构成排列，所以实现思路为将1位置原本的数字和这一段最开始的数字互换，假设一个长度为5的数组，对应s为10001，那么第一段就是1，本身互换所以第一个位置还是1，后面第二段[2,3,4,5]最后一个位置和第一个位置互换得到[5,3,4,2]可以发现我们正好是通过将每段最小值放在最后一个，相当于最后才“补上”缺口形成排列。最后判断是否可以形成排列的逻辑也很简单，那就是我们最后的段没有结束符号“1”，因为本身就是自然数组，所以最后一个必须是1，可以像其他人一样最开始就判断好能不能行，我这个就是单纯根据之前的逻辑，保证最后所有段都结束了。