Description
作为彩虹岛的刀塔大师，lwq很擅长操作中单英雄卡尔。卡尔一共拥有10个技能。在卡尔的10个技能当 中，lwq最擅长的就是“幽灵漫步”。下面，lwq想就切技能的问题考考你： lwq共有QWE三种技能球。假设lwq现在的技能状态是QQW，他每次操作可以弹出第一个球，并在最 后插入一个球。例如lwq现在可以从状态QQW，经过一次操作后变成QWQ,QWW或者QWE。现在lwq给 出了他的初始技能状态和目标技能状态，想让你求出他的最少操作次数。（初始技能状态和目标技能状态恒 为3个球。QWE和WEQ视为同一种状态，即对应技能球数目相同则视为同一状态，位置不用相同。）Input
输入第一行为一个整数T(T ≤ 60)，表示一共有T组测试数据。 对于每组测试数据： 第一行有三个字符a,b,c(a,b,c ∈{Q,W,E})，表示初始技能状态。 第二行有三个字符d,e,f(d,e,f ∈{Q,W,E})，表示目标技能状态。
Output
对于每组测试数据输出一个整数x，表示从初始技能状态到目标技能状态的最少操作次数。Sample Input
2QWE
EEE
WQE
EWQ
Sample Output
20
Hint
对于第一组样例，第一次操作弹出球Q插入球E，第二次操作弹出球W插入球E。 对于第二组样例，初始技能状态和目标技能状态相同，无需操作。
思路：由于初始到目标的操作为从前往后弹出，所以对初始状态从右往左判断，用vis数组保存目标状态的三种技能的个数，扫描初始状态时，将vis数组中对应的单元减一，表示不需要对该技能操作一次，因为技能数不能为负，故若减到-1就跳出，最后求总操作数。
1 #include2 #include 3 #include 4 #include 5 #include 6 #define M 1000005 7 8 using namespace std; 9 char a[M], b[M];10 int main()11 {12 int t;13 cin >> t;14 while (t--)15 {16 int vis[3];17 memset(vis, 0, 3 * sizeof(int));18 for (int i = 0; i < 3; i++) cin >> a[i];19 for (int i = 0; i < 3; i++)20 {21 cin >> b[i];22 if (b[i] == 'Q') vis[0]++; //vis[0]记录Q的个数，如下同理23 if (b[i] == 'W') vis[1]++;24 if (b[i] == 'E') vis[2]++;25 }26 27 for (int i = 2; i >= 0; i--) //对初始状态从右往左扫28 {29 if (a[i] == 'Q')30 {31 vis[0]--;32 if (vis[0] == -1)33 {34 vis[0] += 1; //若减到-1，重置为0，否则最后求和时会出问题35 break;36 }37 }38 if (a[i] == 'W')39 {40 vis[1]--;41 if (vis[1] == -1)42 {43 vis[1] += 1;44 break;45 }46 }47 if (a[i] == 'E')48 {49 vis[2]--;50 if (vis[2] == -1)51 {52 vis[2] += 1;53 break;54 }55 }56 }57 58 int sum = 0;59 for (int i = 0; i < 3; i++)60 {61 sum += vis[i];62 }63 cout << sum << endl;64 }65 return 0;66 }
备注：一开始并没有注意到跳出循环前要对-1重置，觉得最后求和时只要对结果+1即可，但是这种方法会混淆0 0 0和0 -1 0这样的数据，前者相等，操作数为0，后者不相等，操作数为1。