题解 P1124 【文件压缩】
MC_Launcher · · 题解
发一弹题解啦
我第一眼看到这题就懵了，自己模拟一下，诶，有个规律！
什么规律呢，来，我放个图——等等，我先讲一下。
咱们先把输入的那个
接着呢，咱们再接着把这个尾字母变成首字母重复上述过程，到现在，细心的读者朋友们肯定能想到这是怎么回事了：这不是个环吗？首字母其实和尾字母连在一起的！然后一步步把这个环推出来，香！
好的现在可以放图了(作图粗糙，请原谅)。
恩好的大家已经看到一步步怎么推出来的了是吧，剩下就不用我赘术了就可以让我偷懒了
但是呢，我们正着写虽然直观易懂，但是会有错，可能有些字母会错位，我第一次正着排就才10分，所以我们要倒着找，最后反着输出，如果不理解，可以输出中间变量，然后也就懂了。
献上代码+注释
#include<bits/stdc++.h>//可食用头文件
using namespace std;
int main()
{
int n,shou,now;//n为S串长度，shou即为题目中p，首字母所在压缩后的位置，now为现在进行到哪个位置了
cin>>n;//输入
char a[n],b[n],ans[n];//a——压缩串，b——字典序串，ans——答案串
cin>>a>>shou;//万能cin
for(int i=0;i<n;i++)b[i]=a[i];//a带给b
sort(b,b+n);//自动排序
for(int i=0;i<n;i++)//首先按首字母找到最后一个字母
{
if(b[i]==a[shou-1])
{
now=i;
b[i]=')';//标记，退出
break;
}
}
ans[0]=a[now];//计入答案
for(int i=1;i<n;i++)//ans[i]表示倒数第i+1个字母
{
for(int j=n-1;j>=0;j--)//从后往前搜到第一个与原char串匹配的字典序串
{
if(b[j]==a[now])
{
now=j;//更改现在所在位置，即跳到前一个字母
ans[i]=a[now];//计入答案
b[j]=')';//标记
break;
}
}
}
for(int i=n-1;i>=0;i--)cout<<ans[i];//倒序输出
}