1. 问题描述：
小蓝最近学习了一些排序算法，其中冒泡排序让他印象深刻。 在冒泡排序中，每次只能交换相邻的两个元素。小蓝发现，如果对一个字符串中的字符排序，只允许交换相邻的两个字符， 则在所有可能的排序方案中，冒泡排序的总交换次数是最少的。例如，对于字符串 lan 排序，只需要 1 次交换。对于字符串 qiao 排序， 总共需要 4 次交换。小蓝找到了很多字符串试图排序，他恰巧碰到一个字符串，需要 100 次交换，可是他忘了吧这个字符串记下来，现在找不到了。请帮助小蓝找一个只包含小写英文字母且没有字母重复出现的字符串，对该串的字符排序，正好需要 100 次交换。如果可能找到多个，请告诉小蓝最短的那个。如果最短的仍然有多个，请告诉小蓝字典序最小的那个。请注意字符串中不可以包含相同的字符。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个只包含小写英文字母的字符串，在提交答案时只填写这个字符串，填写多余的内容将无法得分。
2. 思路分析：
因为是需要尽可能使用较短长度的字符串来构成100次的相邻字符的交换，并且要求字典序是最小的而且只能交换相邻的字母，所以我们需要使用尽可能使用排列在前面的字符，并且使用逆序排列，考虑完全逆序的情况这样才可以使得字符串的交换次数尽可能多也就是字符串最短，那么需要长度为15的完全逆序的字符串，因为完全逆序交换的次数为：1 + 2 + ... 14 = 105，所以剩下的我们就需要在完全逆序的字符串："onmlkjihgfedcba"进行调整使其构成能够使用100次的相邻字母的字符串，105次只比100次多了5次，所以我们需要将其中多余的5次消除掉，分析字符串的特点可以知道后面字典序较大的字符往前调整，位于其前面的字符串的相对位置是不变的，所以我们需要在逆序的"onmlkjihgfedcba"字符串第6个字母放到最前面，这样当排列好了"abcdefghi"之后j就位于其后面，这样字母j这个位置是不用调整的，所以恰好消除了多余的5次，最后交换的次数为 14 + 13 + ... + 6 + 4 + 3 + 2 + 1 = 100次。所以结果为：jonmlkihgfedcba。主要还是找出其中的规律，先考虑极端的情况再进行调整
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
