题目大意
一个长度为 \(n\) 的字符串 \(S\)，进行以下操作。
假设 \(s\) 为 acbdef，每一次将首字母移至末尾，得到 \(6\) 个字符串：
acbdef
cbdefa
bdefac
defacb
efacbd
facbde
将每个字符串的首字母排序：
acbdef
bdefac
cbdefa
defacb
efacbd
facbde
每个字符串的末尾连在一起为 fcabde，这就是 \(S'\)。
最后让你反推出 \(S\)。
解题思路
- 原串将首字母移至末尾就得到构造串。
- 构造的第一个串就是原串。
- 构造的其余字符串的“末尾字符”是“该串首字母”在“原串 \(ans[\ ]\) ”中的前一个字符。
- 维护 \(cur\) 表示 \(s1[\ ]\) 的位置，则 \(s_{cur}\) 是 \(s1_{cur}\) 的前一个字符。
- 倒序确认原串的位置，因为倒序的字符在 \(s1[\ ]\) 中寻找是有序的，反之正序确认则需要在 \(s[\ ]\) 中找，是无序的。
代码
#include<bits/stdc++.h>
using namespace std;
int n, p, cur;
char s[10005], s1[10005], ans[10005]; // s1表示排序后的串，s表示排序前的串
bool vis[10005];
int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> s[i];
s1[i] = s[i];
}
cin >> p;
sort(s1 + 1, s1 + n + 1);
ans[1] = s[p]; // 首字母确认
for(int i = 1; i <= n; i++) {
if(s1[i] == s[p]) {
cur = i; // 找构造的第一个串编号
break;
}
}
for(int i = n; i >= 2; i--) { // 倒序确认位置
vis[cur] = 1; // 标记s1[cur]已经使用
ans[i] = s[cur]; // 原串i个位置的字母就是s[cur]
for(int j = n; j >= 1; j--) {
if(s1[j] == s[cur] && !vis[j]) {
cur = j;
break;
}
}
}
for(int i = 1; i <= n; i++) {
cout << ans[i];
}
return 0;
}