P8719 [蓝桥杯 2020 省 AB2] 字串排序题解

根据题目意思，我们构造的字符串需要满足冒泡排序交换次数为 $V$ 次，越短越好的情况下输出字典序最小的那一个。于是我们先从字符串的长度开始考虑。

1. 如何求字符串的最短长度是多少

设字符串长度为 $len$, 若该长度的字符串能构造出的最大交换数 $\ge V$，就代表该长度的字符串一定能恰好构造出交换数为 $V$ 的。于是我们首先要求的是长度为 $i$ 的字符串能构造出的的最大交换数 $f_i$ 是多少。

在求最大交换数之前，我们需要知道冒泡排序的一个性质：最大交换数 $=$ 逆序对的个数（下文中就用逆序对数代替最大交换数），长度 $len\le 26$ 的字符串的最大构造方法显然是前 $len$ 个字符按逆序排列，这样逆序对的个数就是 $f_{len}=len\ast (len-1)/2$，这样构造的最大交换数在 $len=26$ 时取得 $f_{26}=325$。
当要求的逆序对数 $\ge 325$ 时怎么办呢？我们考虑字符串的长度每增加一个字符相当于在任意位置插入一个字符，那么最多能得到的新增逆序对数为：原字符串中与新增字符不同的字符个数。

例如：$cbbaa$ 新增一个字符，显然是插入一个 $c$ 在原来的 $c$ 周围最优。 我们可以得出结论：字符串中所有字符数量越接近越好，在字符数 $\ge 26$ 以后就又是以 $abc$ 的顺序开始新增（满足字典序小）,每次插入新字符增加的逆序对即为原字符长度 - 与自己相等的字符数量。

我们可以递推求解长度为 $i$ 的字符串能构造的最大逆序对数为 $f_i$。在确定最短长度后开始考虑其他条件。

2. 如何使得字符串中的逆序对个数恰好为 $V$ 的同时，使得字典序最小。

同样利用上述构造最大逆序对的贪心策略，我们从前向后暴力枚举该位的字符 (从 $a$ 开始枚举，满足字典序最小)，剩下的字符按照逆序对最大的方法进行构造能否使得逆序对数 $f_i\ge V$，如果能就选定该字符，否则就枚举紧接着的下一位字符（具体见代码及注释）。

#include 
using namespace std;
int n;
/*  
贪心的思想，增加字符串长度相当于插入一个字符，增加的逆序对 = 大于自己 + 小于自己的，
最大构造逆序对的情况即不等于自己的字符数，于是有字符串中所有字符数量越接近越好，
在字符数 > 26 以后就又是从abc的顺序开始新增（满足字典序小）,每次插入新字符增加的逆序对即为原字符长度 - 与自己相等的字符数量
于是我们可以暴力枚举字符，判断在选择此字符的情况下能否构造出逆序对数 >= n的
*/
int f[1010];
int get_max(){ // 获取长度为m的字符串的最大逆序对数
    for(int i = 2; i <= 26; i ++) f[i] = f[i - 1] + i - 1; // 长度小于26的字符串最大逆序对数
    int sum = 26, vis[30];
    for(int i = 0; i < 26; i ++) vis[i] = 1; // 记录当前字符串已经各个字符串各一个了
    for(int i = 27; f[i - 1] < n; i ++, sum ++){ 
        int ch = (i % 26 - 1 + 26) % 26; // 新增的字符按abc……的顺序新增，插入到逆序的位置，例如zyx……a,下一个接着插入a zyx……aa
        f[i] = f[i - 1] + sum - vis[ch]; vis[ch] ++; //新增逆序对字符总数 - 和自己相同的字符数
    }
}

int cnt[30], vis[30]; // cnt 代表已经确定的构造字符，vis代表后续按最大方法构造的字符
int get_add(int ch){
    int add = 0;
    for(int i = 0; i < ch; i ++) add += vis[i]; // vis 是还未确定的可以按任意顺序排列所以都可以计算进来
    for(int i = ch + 1; i < 26; i ++) add += cnt[i] + vis[i]; // 因为cnt已经确定了，后续字符只能在其后，所以新增的只能是 > ch 的字符数
    return add; 
}
bool check(int id, int m, int ch, int sum){
    for(int i = id + 1; i <= m; i ++){
        int maxadd = 0, ch1 = 0;
        for(int j = 0; j < 26; j ++){ // 和上述fi的求解过程同理，只是枚举字符选择最优解的那一个
            int add = get_add(j);
            if(maxadd < add){
                maxadd = add;
                ch1 = j;
            }
        }
        vis[ch1] ++;
        sum += maxadd;
    }
    memset(vis, 0, sizeof vis);
    if(sum >= n) return true; // 当剩余字符能构造出 >= n 的即返回true
    return false;
}

void solve(int m){
    int sum = 0;
    string ans;
    for(int i = 1; i <= m; i ++){
        for(int j = 0; j < 26; j ++){ // 每个位置都从'a' 开始枚举，看是否剩下的字符最大情况下仍然能构造出大于等于n的字符，若可以则使用当前的ch
            int initadd = get_add(j);
            cnt[j] ++;
            sum += initadd;
            if(check(i, m, j, sum)){
                ans += ('a' + j);
                break;
            }
            cnt[j] --; // 不满足，于是回溯枚举新的字符
            sum -= initadd;
        }
    }
    cout << ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n;
    get_max();
    for(int i = 2; i <= n; i ++){
        if(f[i] >= n){
            solve(i);
            break;
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

一个贪心的构造题，使用暴力的方法实现，思维确实挺巧妙的。