2574 問題 D: 藍(lán)橋杯2020年第十一屆省賽真題-字串排序
時(shí)間限制: 1s
內(nèi)存限制: 128MB 提交: 421 解決: 44
題目描述
小藍(lán)最近學(xué)習(xí)了一些排序算法，其中冒泡排序讓他印象深刻。在冒泡排序中，每次只能交換相鄰的兩個(gè)元素。小藍(lán)發(fā)現(xiàn)，如果對一個(gè)字符串中的字符排序，只允許交換相鄰的兩個(gè)字符，則在所有可能的排序方案中，冒泡排序的總交換次數(shù)是最少的。
例如，對于字符串 lan 排序，只需要 1 次交換。對于字符串 qiao 排序，
總共需要 4 次交換。小藍(lán)找到了很多字符串試圖排序，他恰巧碰到一個(gè)字符串，需要 V 次交換，可是他忘了把這個(gè)字符串記下來，現(xiàn)在找不到了。
請幫助小藍(lán)找一個(gè)只包含小寫英文字母且沒有字母重復(fù)出現(xiàn)的字符串，對該串的字符排序，正好需要 V 次交換。如果可能找到多個(gè)，請告訴小藍(lán)最短的那個(gè)。如果最短的仍然有多個(gè)，請告訴小藍(lán)字典序最小的那個(gè)。請注意字符串中可以包含相同的字符。
輸入
輸入的第一行包含一個(gè)整數(shù)V，小藍(lán)的幸運(yùn)數(shù)字。
提示
對于30% 的評測用例，1 ≤ n ≤ 20；
對于50% 的評測用例，1 ≤ n ≤ 100；
對于100% 的評測用例，1 ≤ n ≤ 10000；