A7046. 插入一位数字
编程题
普及-
知识点
题目描述
给定一个长度为 $n$ 的十进制数字串 $s$（表示一个非负整数，允许 $s=0$），以及一个数字 $d$（$0\le d\le 9$）。你需要**将数字 $d$ 恰好插入一次**到 $s$ 的某个位置（可以在最前面或最后面），使得得到的新数字**尽可能大**。输出这个新数字对应的字符串。
插入规则等价于：从左到右扫描 $s$，找到第一个满足 $s_i \lt d$ 的位置，把 $d$ 插入到该位置之前；如果不存在这样的 $i$，则将 $d$ 追加到末尾。
插入规则等价于：从左到右扫描 $s$，找到第一个满足 $s_i \lt d$ 的位置，把 $d$ 插入到该位置之前；如果不存在这样的 $i$，则将 $d$ 追加到末尾。
输入格式
第一行：一个整数 $n$（$1\le n\le 2\times 10^5$），表示字符串 $s$ 的长度。
第二行：一个仅由字符
第三行：一个字符 $d$，为
第二行：一个仅由字符
'0'$\sim$'9' 组成的字符串 $s$，长度为 $n$。当 $n>1$ 时，$s$ 无前导零。第三行：一个字符 $d$，为
'0'$\sim$'9' 之一。输出格式
输出将 $d$ 插入一次后得到的、数值最大的字符串。
输入输出样例
输入 #1
3 123 5
输出 #1
5123
输入 #2
3 789 6
输出 #2
7896
输入 #3
5 11111 1
输出 #3
111111
说明/提示
$1\le n\le 2\times 10^5$