试题J 字串排序

题目提交点

点我进入官网提交题目

【问题描述】

小蓝最近学习了一些排序算法，其中冒泡排序让他印象深刻。
在冒泡排序中，每次只能交换相邻的两个元素。小蓝发现，如果对一个字符串中的字符排序，只允许交换相邻的两个字符，则在所有可能的排序方案中，冒泡排序的总交换次数是最少的。
例如，对于字符串 lan 排序，只需要 1 次交换。对于字符串 qiao 排序，总共需要 4 次交换。
小蓝找到了很多字符串试图排序，他恰巧碰到一个字符串，需要 V 次交换，可是他忘了把这个字符串记下来，现在找不到了。
请帮助小蓝找一个只包含小写英文字母且没有字母重复出现的字符串，对该串的字符排序，正好需要 V 次交换。如果可能找到多个，请告诉小蓝最短的那个。如果最短的仍然有多个，请告诉小蓝字典序最小的那个。请注意字符串中可以包含相同的字符。

【输入格式】

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

【输出格式】

题面要求的一行字符串。

【样例输入】

4
1

【样例输出】

bbaa
1

【样例输入】

100
1

【样例输出】

jihgfeeddccbbaa
1

【评测用例规模与约定】

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

思路

• 首先我们要考虑：相同长度下，什么样的字符串符合短、字典序小而且交换次数最多？
  符合$s[i-1]\ge s[i]$性质的字符串。
• 然后贪心考虑完了， 题目中又有最小类字眼，所以考虑DP。
  DP为二维，$f[i][j]$表示： 长度为i, 且以字母j - 1 + 'a'开头的字符串交换次数的集合。 求最大值。
  动态转移方程一般都是从前一个状态考虑， 那么$f[i][j]$就可以从$f[k][j-1]k\in (1,i-1)$ 转化过来。
  因为 $k<i$，长度不够且要结果最大，所以假设他前面有（i - k）个最小的字符，那么，每次都要向后面移动k 次，所以还需要加上 $k\ast (i-k)$。
  数组只要开200就够了， 在不考虑26个字母的情况下， $i\ast (i-1)=v$ , 但是题目中只能是小写字母，所以字符串中可能会出现相同的字符，那么就会将字符串长度拉长， 所以保险起见i 最大取值为200。
• 最后输出DP具体方案。

代码

#include<bits/stdc++.h>
using namespace std;

#define _for(i, a, b) for (int i = (a); i < (b); ++i)
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define For(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(a) cout << #a << " = " << a << endl;
#define mod(x) (x) % MOD
#define ENDL "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<int> vi;

const int N = 200 + 10, M = 30;
int f[N][M], n;

void get(int& a, int& b) {
    _for(i, 0, N) _rep(j, 1, 26) if (f[i][j] >= n) {
        a = i, b = j;
        return;
    }
}

int main()
{
#ifdef LOCAL
    freopen("data.in", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cout.tie(0), cin.tie(0);
    
    memset(f, -0x3f, sizeof f), f[0][0] = 0;
    cin >> n;
    _for(i, 0, N) _rep(j, 1, 26) _for(k, 0, i) 
        f[i][j] = max(f[i][j], f[k][j - 1] + k * (i - k));

    int len = 0, alp = 0, same = 0;
    get(len, alp);

    while (len) {
        if (alp == 1) cout << 'a';
        else if (f[len][alp - 1] >= n)
            alp--, cout << char(alp - 1 + 'a'), n -= len - 1, same = 1;
        else cout << char(alp - 1 + 'a'), n -= len - 1 - same, same++;
        len--;
    }

    return 0;
}