题目相关

题目链接

AtCoder Grand Contest 048 A 题，https://atcoder.jp/contests/agc048/tasks/agc048_a。

Problem Statement

Given is a string S consisting of lowercase English letters. Snuke can do the operation of swapping two adjacent characters in S. For example, if S=agc, one operation can change it to gac (by swapping a and g) or acg (by swapping g and c).

Snuke wants to do this operation zero or more times so that atcoder <S holds lexicographically.

The definition of the lexicographic relation x<y

Determine whether the objective is achievable. If it is achievable, find the minimum number of operations needed. Solve T test cases in an input file.

Input

Input is given from Standard Input in the following format. The first line of input is as follows:

T

Then, T test cases follow, each of which is in the following format:

S

Output

For each test case, print −1 if the objective is unachievable, and print the minimum number of operations needed if it is achievable. Use one line for each case.

Samples1

Sample Input 1

3 atcodeer codeforces aaa

Sample Output 1

1 0 -1

Explaination

The first test case: for example, swapping the last two characters makes S=atcodere > atcoder hold.The second test case: before doing any operation, we already have S=codeforces > atcoder.The third test case: no sequence of operations makes S> atcoder hold.

Constraints

1 ≤ T ≤ 1001 ≤ |S| ≤ 1000S is a string consisting of lowercase English letters.

题解报告

题目翻译

给一个全部由小写字母组成的字符串 S。高桥可以讲相邻的两个字母交换位置，比如字符串 agc，可以 gac（交换 g 和 a 的位置），也可以变为 gca（交换 a 和 c 的位置）。

高桥希望通过零次或者若干次操作，最终能使得字符可以满足 s > atcoder，使用字典序排序。

要求我们知道最少的交换次数。

基础知识

字典序

在数学中，字典或词典顺序（也称为词汇顺序，字典顺序，字母顺序或词典顺序）是基于字母顺序排列的单词按字母顺序排列的方法。也就是说小写字母 a<b<c<...<z。

字符串排序

字符串排序是从头开尾，每个字符按照字典序进行排序。假设我们有两个字符串 a 和 b。

如果 a[i]>b[i]，则字符串 a>b；如果 a[i]<b[i]，则字符串 a<b；如果所有的 a[i]==b[i]，则字符串 a==b。

从代码实现角度看，我们可以使用循环遍历字符串 a 和 b，进行每个字符逐一比较；也可以使用 STL 的 string 类，string 类直接重载了比较操作符，相对来说比较简单。

题目分析

本题的核心问题是字符串排序，而且本题是求解方案数，这样本题又变成纯粹的数学题。

我们题目的要求是：移动相邻的两个字符；同时知道最终要比较的字符串是 atcoder。这样我们可以分析出如下规律：

1、第一个字符为 a。根据字典序排序规则可知，没有小写字母能大于 a。

2、第二个字符为 t。根据字典序排序规则可知，排在字母 t 前都小于 t；排列在字母 t 后的，都大于 t。

什么意思？我们来看以下下面的几个实例：

1、b；

2、z；

3、aa；

4、ab；

5、as；

6、at；

7、au；

8、az；

9、ata；

10、atb；

11、atz。

对于实例 1。不需要移动已经满足题目的呀求。

对于实例 2。不需要移动已经满足题目的呀求。

对于实例 3。不管怎么移动，都不可能满足题目的呀求。

对于实例 4。我们只需要我们变为 ba 即可，因为 ba>atcoder。

对于实例 5。我们只需要我们变为 sa 即可，因为 sa>atcoder。

对于实例 6。我们只需要我们变为 ta 即可，因为 ta>atcoder。

对于实例 7。因为 au>atcoder。移动次数为零。

对于实例 8。因为 az>atcoder。移动次数为零。

对于实例 9。我们只需要我们变为 taa 即可，因为 taa>atcoder。注意移动的方法和 4、5、6 不一样，这里我们移动前面。

对于实例 10。我们只需要我们变为 tab 即可，因为 tab>atcoder。注意移动的方法和 4、5、6 不一样，这里我们移动前面。

对于实例 11。我们只需要我们变为 taz 即可，因为 taz>atcoder。注意移动的方法和 4、5、6 不一样，这里我们移动前面。

算法设计

通过上面分析。我们可以分类讨论字符 S 和 atcoder 关系。首先我们看两个特殊情况。

特例一：S 本身已经大于 atcoder

对于这样的输入，已经满足题目要求。因此输出 0。

特例二：S 全部为字母 a

对于这样的输入，参考分析的样例 3，我们知道不管怎么移动都不能满足要求。因此输出 -1。

通例

通过观察，我们假设输入字符串 S 的第零个字符到第 i-1 个字符全部为 a，第 i 个字符为 x。

如果 a[i]<='t'，如实例 4、5、6，我们只需要交换字符 a[i] 和 a[0] 就可以满足要求。也就是进行了 i 次交换。

如果 a[i]>'t'，如实例 9、10、11，我们只需要交换字符 a[i-1] 和 a[0] 就可以满足要求。也就是进行了 i-1 次交换。

AC 参考代码

这里我使用 string，比较方便。

//https://atcoder.jp/contests/agc048/tasks/agc048_a //A - atcoder < S #include <bits/stdc++.h> using namespace std; int main() { int t; cin>>t; string str; while (t-->0) { cin>>str; //特例判断 if (str>"atcoder") { cout<<"0\n"; continue; } else { string tmp(str.length(), 'a'); if (str==tmp) { cout<<"-1\n"; continue; } } for (int i=0; i<str.length(); i++) { if ('a'==str[i]) { continue; } if (str[i]<='t') { cout<<i<<"\n"; break; } else { cout<<i-1<<"\n"; break; } } } return 0; }

时间复杂度

算法的时间复杂度为：O(T*S)。