主要思想参考这个博客字串排序
也就是字符串中字符的数量尽可能相等,所带来的逆序对是最多的。
所以首先枚举字符串的最小长度len,满足
$((len - (len / 26 + 1)) * (len / 26 + 1) * (len \% 26) +
(len - len / 26) * (len / 26) * (26 - len \% 26)) \div 2 >= m$
其次确定最小字典序,从字符串的第一个位置到最后一个位置考虑放哪个字符。
依次从小到大枚举字符c = [a~z],判断当前放c,可以带来的最大逆序对数量是否大于等于$m$。
如果大于,该位置就放c,这时候一定是最小的。
接下来就是如何计算可以带来的最大逆序对数量了。
我们设当前位置是$x$,$add1$表示$[1, x - 1]$中大于c的数量。
然后依次枚举区间[x + 1, k] (k <= len)中放哪些字符,假设当前位置k放字符$j$,那么能带来的最大逆序对是:
(k - x - 1) - $[x + 1, k - 1]$中与$j$相等的字符数量 + $[1, x]$中小于$j$的数量。
最后判断$now + add1 + add2$与$m$的大小关系,其中now表示下标在[1, x - 1]字符带来的逆序对数量。
时间复杂度:O(26n)
#include <bits/stdc++.h>
using namespace std;
const int N = 30;
int sum[N], cnt[N], len, now;
int m;
int get(int len) {
return ((len - len / 26 - 1) * (len % 26) * (len / 26 + 1)) / 2 + (len - len / 26) * (26 - len % 26) * (len / 26) / 2;
}
bool check(int c, int n) {
memset(cnt, 0, sizeof cnt);
int add1 = 0, add2 = 0;
for(int j = 25; j > c; -- j) add1 += sum[j];
sum[c] ++;
for(int i = 1;i <= n; ++ i) {
int maxd = -1, pos, num = 0;
for(int j = 25; j >= 0; -- j) {
if(i - 1 - cnt[j] + num > maxd) {
maxd = num + i - 1 - cnt[j];
pos = j;
}
num += sum[j];
}
add2 += maxd, cnt[pos] ++ ;
}
if(now + add1 + add2 >= m) {
now += add1;
return true;
}
else {
sum[c] -- ;
return false;
}
}
int main() {
cin >> m;
for(len = 1; ; len ++ ) {
if(get(len) >= m) {
break;
}
}
string ans = "";
for(int i = 1;i <= len; ++ i) {
for(int j = 0;j < 26; ++ j) {
if(check(j, len - i)) {
ans += char(j + 'a');
break;
}
}
}
cout << ans << endl;
return 0;
}
orz
orz