首页 > 试题广场 >

小红的排列构造②

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

热度指数：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

说明

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

算法知识视频讲解

_KOKORO_

发表于 2025-04-10 12:31:27

思路就是维护一个全局数字 k 初始为 1。遇到字符串里有 '1' 就倒序遍历填充并让 k++如 00101，第一次遇到 '1' 答案数组变成 3 2 1 0 0，第二次遇到 '1' 变成 3 2 1 5 4 import java.util.Scanner; // 注意类名必须为 Main, 展开全文

牛客856751393号

发表于 2025-03-07 11:45:27

while True: try: n = int(input()) s = input() if s[-1] == '0': print(-1) else: res = [i fo 展开全文

在写文章的小白菜很犯困

发表于 2025-06-02 20:58:11

观察到以下规律：如果[1, 2, ... , n]的第k<n位和最后一位交换，那么[0,n)依旧是一个排列，而[0,k]不是一个排列。所以算法如下：从1 2 3 4 5 ... n开始对每个'0'的位置 i，总是找其后面的第一个'1'位置 j，交换perm[i],perm[j]。 #inclu 展开全文

番禺小韭菜

发表于 2025-03-04 16:47:05

#include <iostream> #include <string> #include <vector> using namespace std; int main() { int n; string s; cin >> 展开全文

我是芭芭拉的狗

发表于 2026-01-05 21:46:54

n = int(input()) a = input() z = 1 c = 0 y = 0 if a[-1] == '0': print('-1') exit() for i in a: if i == '1': if y == 0: 展开全文

BraveCoder

发表于 2025-10-16 19:56:28

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n 展开全文

牛客215801247号

发表于 2025-03-06 23:22:07

import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in. 展开全文

吴昊9873

发表于 2025-05-05 14:06:41

#include <stdio.h> int main() { int n; scanf("%d", &n); char str[n]; int arr[n]; for (int i = 0; i < n; i+ 展开全文

牛客277605456号

发表于 2025-04-12 14:34:34

写了好久的递归调用dfs，结果超时了，一看答案感觉自己像小丑，记录一下n = int(input()) s = input() if s[-1] != '1': print(-1) else: def deal(arr:list, s:str, arr2:list): 展开全文

甘肃农业大学_zrk

发表于 2025-10-21 14:01:43

#include <bits/stdc++.h> using namespace std; int main() { int n;cin>>n; string s;cin>>s; if(s.back()=='0'){ cou 展开全文

问题信息

模拟

难度：

29条回答 87收藏 550浏览

小红的排列构造②

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

相关试题