solution.md

# 字串排序


**问题描述**

小蓝最近学习了一些排序算法，其中冒泡排序让他印象深刻。  

在冒泡排序中，每次只能交换相邻的两个元素。小蓝发现，如果对一个字符串中的字符排序，只允许交换相邻的两个字符，则在所有可能的排序方案中，冒泡排序的总交换次数是最少的。 

例如，对于字符串 lan 排序，只需要 1 次交换。对于字符串 qiao 排序，总共需要 4 次交换。  

小蓝找到了很多字符串试图排序，他恰巧碰到一个字符串，需要 V 次交换，可是他忘了把这个字符串记下来，现在找不到了。  

请帮助小蓝找一个只包含小写英文字母且没有字母重复出现的字符串，对该串的字符排序，正好需要 V 次交换。如果可能找到多个，请告诉小蓝最短的那个。如果最短的仍然有多个，请告诉小蓝字典序最小的那个。请注意字符串中可以包含相同的字符。  



**输入格式**

输入的第一行包含一个整数V，小蓝的幸运数字。


**输出格式**

题面要求的一行字符串。


**样例输入**

```
4
```

**样例输出**

```
bbaa
```

**样例输入**

```
100
```

**样例输出**

```
jihgfeeddccbbaa
```

**评测用例规模与约定**

```
对于 30% 的评测用例， 1 ≤ V ≤ 20。
对于 50% 的评测用例， 1 ≤ V ≤ 100。
对于所有评测用例， 1 ≤ V ≤ 10000。
```

下面的程序实现了这一功能，请你补全空白处内容：

```c
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
int dp[152][26][152];
int dfs(int pre, int x, int aft)
{
    int &d = dp[pre][x][aft];
    if (~d)
        return d;
    if (x == 1)
        return d = pre * aft;
    if (aft == 0)
    {
        if (x != 0)
            return -1e9;
        return 0;
    }
    int ans = 0;
    for (int i = 1; i <= aft; i++)
    {
        int res = dfs(pre + i, x - 1, aft - i) + i * pre;
        if (ans < res)
        {
            ans = res;
        }
    }
    return d = ans;
}
void dfs2(int pre, int x, int aft, int rest, string &res)
{
    if (x == 1)
    {
        res += string(aft, 'a');
        return;
    }
    int len = 1e9;
    for (int i = 1; i <= aft; i++)
    {
        int d = dfs(pre + i, x - 1, aft - i) + i * pre;
        if (d >= rest)
        {
            len = i;
            break;
        }
    }
    res += string(len, 'a' + x - 1);
    rest -= len * pre;
    __________________
    return;
}
int calc(string a)
{
    int n = a.size();
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (a[i] > a[j])
                ans++;
        }
    }
    return ans;
}
void solve(int v)
{
    memset(dp, -1, sizeof dp);
    int len = 1e9, x = 1e9;
    for (int i = 1; i <= 150; i++)
    {
        for (int j = 1; j <= 26; j++)
        {
            if (dfs(0ll, j, i) >= v)
            {
                if (len > i)
                {
                    len = i, x = j;
                }
                else if (len == i)
                {
                    x = min(x, j);
                }
            }
        }
    }
    string ans;
    dfs2(0, x, len, v, ans);
    cout << ans << endl;
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    solve(n);
    return 0;
}
```


## 答案

```c
dfs2(pre + len, x - 1, aft - len, rest, res);
```

## 选项

### A

```c
dfs2(pre + len, x, aft - len, rest, res);
```

### B

```c
dfs2(pre + len, x - 1, aft - 1, rest, res);
```

### C

```c
dfs2(pre + len, x - 1, aft, rest, res);
```