地址 https://www.papamelon.com/problem/213
给定一个字符 SS,长度为 NN。由 SS 构成出新的字符串 TT,长度也为 NN。
起初 TT 是一个空串,然后执行 NN 次操作,每次操作有两种选择:
从 S 头部删除一个字符,加到 T 的尾部
从 S 尾部删除一个字符,加到 T 的尾部
我们要决定一种最优的操作方案,使得 T 串的字典序最小。
输入
第一行整数 N(1≤N≤2000),表示 S 串的长度
接下来 N 行,每行一个大写英文字符,表示 S 串的每个字符
输出
输出一行或多行:每行最多 80 个字符,当 T 串太长,需要换行再继续输出
样例 1
输入
6
A
C
D
B
C
B
输出
ABCBCD
解答
贪心算法
从字符串S中左右两端取出字典序较小的那个 放入T中 比如 s= acdb 那么最后 t=abcd
需要考虑的特殊情况就是 两边都相同的情况下 s= abccccba,那么需要左右双指针同时向中间移动监测,直到某一边出现了字典序较小的结果,或者两端相遇 那就随机选择