首页 > 试题广场 >

小红的排列构造②

[编程题]小红的排列构造②

热度指数：4103 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 小红定义一个仅由 $\texttt{0}$ 和 $\texttt{1}$ 两个字符构成的字符串 $s$ 与一个长度为 $n$ 的数组 $p$ 为匹配，当且仅当满足下列两点：
${\hspace{20pt}}_\texttt{1.}\,$ 若 $s_i=\texttt{1}$ ，则数组 $\{p_1,p_2,\dots,p_i\}$ 恰好构成一个排列；
${\hspace{20pt}}_\texttt{2.}\,$ 若 $s_i=\texttt{0}$ ，则数组 $\{p_1,p_2,\dots,p_i\}$ 无法构成一个排列。

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

$\hspace{15pt}$ 【名词解释】
$\hspace{23pt}\bullet\,$ 排列：排列是由 $1\sim n$ 这 $n$ 个整数按任意顺序组成的数组，其中每个整数恰好出现一次。

输入描述:

第一行输入一个整数  表示字符串及排列的长度。 
第二行输入一个长度为 ，仅由  和  构成的字符串 。

输出描述:

如果不存在满足条件的排列，直接输出 ；否则，在一行上输出  个整数  表示你构造出的排列。 
如果存在多个满足条件的排列，输出任意一个均可，系统将自动判定其正确性。请注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

示例1

输入

3
001

输出

3 1 2

说明

对于这个样例，
由于 ，排列的前一项元素无法构成一个排列；
由于 ，排列的前两项元素无法构成一个排列；
由于 ，排列的前三项元素构成一个排列；
同时，输出 、 等答案也都是合法的。

示例2

输入

4
1110

输出

-1

说明

在此样例中，若存在合法排列，则前三位必须依次形成排列，但第四位又要求整体不形成排列，显然不可能，因此答案为 。

算法知识视频讲解

Python3

Chinry

import sys

n=int(input())
s=list(map(int,input()))
if s[-1]==0:
    print("-1")
    sys.exit()
num_list=[i for i in range(1,n+1)]
output_list=[0 for i in range(1,n+1)]
count=0
for idx,flag in enumerate(s):
    if flag==1 and idx==0:
        output_list[0]=1
    elif idx>=1 and flag==1 and s[idx-1]==1:
        output_list[idx]=idx+1
    elif flag==0:
        count+=1
    elif flag==1 and count>0:
        output_list[idx-count:idx]=[i for i in range(idx+1,idx-count,-1)]
        count=0
print(' '.join(map(str,output_list[:n])))

发表于 2025-12-16 20:47:17 回复(0)

Python3

不想泡池子的马后炮炮手在看机会

n = int(input())
s = input()
ls = [i for i in range(1,n+1)]
i = 0
flag = True
if s[-1] == '0':
    flag  = False
while i<n and flag:
    if s[i] == '0':
        nex = s.find('1',i)
        if nex==None:
            flag = False
            break
        tmp = ls[i]
        ls[i] = ls[nex]
        ls[nex] = tmp
        i = nex
        continue
    i += 1

if flag:
    for x in ls:
        print(x,end=' ')
else:
    print(-1)

发表于 2025-10-10 12:01:03 回复(0)

Python3

牛客831725372号

def run(mStr, n,l):

if mStr.endswith('0'):

return None

for index in range(n):

if mStr[index] == '1':

pass

else:

l[index] ,l[index+1] = l[index+1] ,l[index]

return l

num = int(input())

mStr = input()

l = [i for i in range(1,num+1)]

res = run(mStr,num,l)

if res:

print(' '.join( [str(i) for i in res] ))

else:

print(-1)

发表于 2025-06-08 15:46:00 回复(0)

Python3

东凡

import sys

n = int(input())

s = input()

#核心，分解成00....01的子序列，然后翻译

split_list = []

while s != '':

temp = ''

while True:

if s[0] == '0':

temp += '0'

if len(s) != 1 :

s = s[1::]

else:

s = ''

break

else:

temp +='1'

if len(s) != 1:

s = s[1::]

break

else:

s = ''

break

split_list.append(temp)

temp = split_list[-1]

if temp[-1] == '0':

print(-1)

else:

s = ''

sum = 0

for i in range(len(split_list)):

if i == 0:

for j in range(len(split_list[0])):

s += str(len(split_list[0])-j)

s += ' '

sum += len(split_list[0])

else:

sum += len(split_list[i])

for j in range(len(split_list[i])):

s += str(sum-j)

s += ' '

print(s)

发表于 2025-03-30 17:00:54 回复(0)

Python3

牛客355368210号

n, s = int(input()),input()

N = len(s)

def _solve():

if s.endswith("0"):

return "-1"

oi = [-1]

for i in range(N):

if s[i] == "1":

oi.append(i)

no = len(oi)

d = [0] * n

for i in range(no - 1, 0, -1):

num = oi[i] + 1

index = oi[i - 1] + 1

d[index] = k = num

for j in range(index + 1, num):

k -= 1

d[j] = k

return " ".join(map(str,d))

def solve():

res = _solve()

print(res)

solve()

发表于 2025-03-05 15:08:24 回复(0)

提交观点

问题信息

模拟

难度：

6条回答 87收藏 546浏览

小红的排列构造②

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

相关试题