P1124 文件压缩　题解

· · 题解

挺有难度的一道模拟题。

以样例为例，在排列并排序后，我们省略中间的字母，是这样的：

a-----x
e-----e
e-----l
l-----p
m-----a
p-----m
x-----e

可以发现，首字母与尾字母是可以相对应的。

样例中 p=7，我们可以立刻知道，原字符串首字母是 e，然后是其对应的 x；然后找到尾字母是 x 的，知道对应的首字母是 a……以此类推，就可以得到 example。

所以我们只要将尾字母排序就会得到首字母了。

但是，当我们在找对应的字母时，正推字母会乱，举个例子：

5
yxxxx
4

按上面的操作，我们会得到：

x---y
x---x
x---x
x---x
y---x

那这样子去操作，不同的写法会得到不同的答案。

因此，我们选择倒推，来避免这种现象。

AC Code：

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

int main()
{
    int n,p,now;
    string s;
    cin>>n>>s>>p;
    string t=s;
    sort(t.begin(),t.end());
    for(int i=1;i<=n;i++)
    {
        if(t[i]==s[p-1])
        {
            now=i;
            t[i]='$';//标记，下同
            break;
        }
    }//先推出最后一个字母
    string ans;
    ans.resize(10005);
    ans[0]=s[now];
    for(int i=1;i<n;i++)
    {
        for(int j=n-1;j>=0;j--)
        {
            if(t[j]==s[now])
            {
                now=j;
                ans[i]=s[now];
                t[j]='$';
                break;
            }
        }   
    }
    for(int i=n-1;i>=0;i--)//倒序输出
    {
        cout<<ans[i];
    }
    return 0;
}