题解 P1124 【文件压缩】 （字符串+思维/模拟）

这道题的基本思路简单来说就是：

• 给定字符串(S1)，所以字符串中字母我们都已经得到了。

• 因为字符串排列的各种情况是按首位排序的，那么我们对其进行排序，得到字符串(S2)，也就得到了各种情况下字符串的首位。

• 每种情况中末位字符在原字符串中下一个字符就是本情况首位字符没问题吧，我们知道了了第一个字符，进而不断递推，由当前一个推出下一个求出原字符序列。 这是正着推。

但是我在此解释一下为什么不能正着推，我遇到了这个问题，题解中和讨论中我没有找到解释，并且又有很多人有疑问。

• 正着推的话，我们先由给出的p确定出第一个字符，与其对应的字符串首位是下一个字符，然后再在给出的字符串(S1)中找出该字符，通过下标相等得到(S2)中对应的字符，即他后一位的字符，就这样不断循环，直到确定出原字符串的所有字符。

• 但是这有一个问题，每次在(S1)中找字符时候，(S1)是无序的，所以找到(S1)中的某个字符时可能并不能接上已经确定的答案字符串。

有一组数据：

4
baab
2

正确答案：

aabb

自己手模一下就可以发现正着推的问题了。

所以我们倒着推可以避免这个问题。

• 首先由第一个字符在(S2)中的位置得到(S1)中相等下标的字符，即答案中的最后一个字符;

• 然后在(S1)中找到相同的字符，再得到(S2)中对应的的字符。是倒数第二个，以此类推。

这样每次找字符时都是从有序序列中找，不会错位。

代码及注释如下：

#include <bits/stdc++.h>
using namespace std;
const int maxn=10000+5;
int n,p;
char s[maxn],ss[maxn]; // s[]是题目给的，ss[]是你排出的对应的各中情况中的首位
char ans[maxn];
int main(){
	//freopen("1.in","r",stdin);
	scanf("%d%s%d",&n,s+1,&p);
	memcpy(ss+1,s+1,sizeof s);
	sort(ss+1,ss+1+n); // 对原字符串排序得到首位
	int cnt=n+1; //cnt 用于记录答案
	for(int i=1;i<=n;++i) if(ss[i]==s[p]) { p=i;break; } //找到 s[p] 即答案中最后一个字符
	while(cnt>1){ // 不能正着推，因为正着推肯定得从给你的序列中按顺序找，但是给你的序列无序
		ans[--cnt]=s[p]; //将s[p]作为当前未确定的答案的最后一位
		ss[p]='#';//ss[p] 是 s[p]的前一位，确定s[p]前一步是确定ss[p],他们下标相同(都是p)。 现在s[p]已记录，ss[p] 没用了，为了防止重复选，置为'#'
		for(int i=n;i>=1;--i) if(ss[i]==s[p]) {p=i;break;} //找到一个与本次while的s[p]相同的一个ss[p],进而推出s[p]的前一位
	}						           //因为找ss[p]是在ss[]中，ss有序，所以不会算重
	printf("%s
",ans+1); 
	return 0;
}