题解 P1124 【文件压缩】

· · 题解

好久没发题解了，来发一波，延续我的 Blog 梦（

Part1 推导过程

从题目中得知，数据给出的排序后的字符串的尾字母。由于它是一个环，这肯定覆盖了所有字符，给它们排一下序，便是首字母了。


    首字母 尾字母
    a   x
    e   e
    e   l
    l   p
    m   a
    p   m
    x   e

我们根据给定的位置，找到尾字母对应的首字母，即 x。由于它是一个环，首字母就是下一个字母啦！

然后找到与当前首字母 x 相同的尾字母，再看对应的首字母，为 a。

一步一步推下去，得到 example 。

Part2 Code

/*
  Author: BreakPlus
  Online Judge: Luogu
  Problem: P1124
  Date: 2020/8/31
*/
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>

typedef long long ll;
typedef std::pair<int,int> P;

#define ls pos<<1
#define rs pos<<1|1
#define maxn 100100
int len,p;
char a[maxn];int now;
char b[maxn],c[maxn];
using namespace std;
signed main()
{
  cin>>len>>a>>p;
  for(register int i=0;i<len;i++) b[i]=a[i];
  sort(b,b+len);
  for(register int i=0;i<len;i++)
    if(b[i]==a[p-1])
    {
      b[i]='@';
      now=i;
      break;
    }
  c[0]=a[now];
  for(register int i=1;i<len;i++)
  {
    for(register int j=len-1;j>=0;j--)
    {
      if(b[j]==a[now])
      {
        now=j;
        c[i]=a[now];
        b[j]='@';
        break;
      }
    }
  }
  for(register int i=len-1;i>=0;i--) putchar(c[i]);
  puts("");
  return 0;
}