A4600 | 字典序问题
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
有 $n$ 个字符串，每个字符串由其下标的整数构成。例如：
当 $n = 100$ 的时候，字符串为 $S_1 = "1", S_2 = "2", S_3 = "3"……，S_{50} = "50",……， S_{100} = "100"$。现在让你在这些字符串中，找到「字典序」最大的字符串。
「字典序」：是基于字母顺序排列的单词按字母顺序排列的方法。例如：对于数字1、2、3......n的排列，不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。例如对于5个数字的排列 12354和12345，排列12345在前，排列12354在后。按照这样的规定，5个数字的所有的排列中最前面的是12345，最后面的是 54321。
$\large{数据范围}$
- $1 \leq n \leq 10^{1000000}$
当 $n = 100$ 的时候，字符串为 $S_1 = "1", S_2 = "2", S_3 = "3"……，S_{50} = "50",……， S_{100} = "100"$。现在让你在这些字符串中，找到「字典序」最大的字符串。
「字典序」：是基于字母顺序排列的单词按字母顺序排列的方法。例如：对于数字1、2、3......n的排列，不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。例如对于5个数字的排列 12354和12345，排列12345在前，排列12354在后。按照这样的规定，5个数字的所有的排列中最前面的是12345，最后面的是 54321。
$\large{数据范围}$
- $1 \leq n \leq 10^{1000000}$
输入格式
输入一个整数代表 $n$
输出格式
输出一个字符串占一行，代表在 $n$ 个字符串中字典序最大的字符串。
输入输出样例
输入 #1
10
输出 #1
9
由于 $n$ 等于10，那么我们的字符串有 $S_1= 1, S_2= 2, S_3= 3, S_4= 4,……, S_{10} = 10$,在这十个字符串里面字符串的字典序最大的是 $S_9 = 9$
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？