思路参考博客 https://blog.csdn.net/weixin_46266058/article/details/123469287

和博客的不同之处在于求最短长度时用了公式推导，设$f(n)$为字串长度为$n$时，逆序对最多的个数（ab算两个逆序对），则有
$$f(n+1) = f(n) + 2*n + (2*n)/26$$

可以自己试着给一个字串加上一个新字符，这样比较容易理解。

求得字串最小长度后，从小到大枚举每个位置的字符，用check函数看最优情况下能否容得下这个字符。
(不过我感觉求add2的时候求的是每个位置的局部最大值而不是n个位置的最大值，想证明这两个等价发现不会证…)

代码如下：

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;

const int N = 30;
int get_r[N];//当前构造部分字符串包含字母a~z的个数
int cnt[N]; //后续部分新增的

string str;
int len; //构造的字符串的长度
int m; //幸运数字
int pr_get; //之前已有的逆序对数量

//在当前位置放c，后续还有n个位置，看是否能满足题目要求
bool check(int c,int n) 
{
    memset(cnt,0,sizeof cnt);
    int add1 = 0, add2 = 0;
    for(int i = c+1;i<26;i++) add1 += get_r[i]; //加入c后，增加的逆序对数量
    get_r[c]++;

    //通过求局部最大值，求add2的最大值
    for(int i  =1;i<=n;i++)
    {
        int maxx = -1;//局部最大值
        int num = 0;//比j小的数个数
        int pos = -1; //选取的数
        for(int j = 25;j>=0;j--) //选取字母,从大到小循环
        {
            if(i - 1 - cnt[j] + num >maxx){ //只减去自己，疑似后面的数一定大于等于前面的数
                maxx = i - 1 - cnt[j] + num;
                pos = j;
            }
            num += get_r[j];
        }
        add2 += maxx, cnt[pos] ++;
    }

    if(pr_get + add1 + add2 >= m)
    {
        pr_get += add1;
        return true;
    }
    else {
        get_r[c] --;//取消选择
        return false;
    }
}

int main()
{
    string ans = "";
    cin>>m;
    int sum = 0;
    for(len = 1; ;len ++)
    {
        sum = sum + 2*len - (2*len)/26;
        if(sum>=2*m) break;
    }
    len ++;
    for(int i = 1;i<=len;i++) //构造字符串
        for(int j = 0;j<26;j++){
            if(check(j,len - i)){
                ans += (char)('a'+j);
                break;
            }
        }
    cout<<ans<<endl;
    return 0;
}