“浪潮杯”山东省第九届ACM大学生程序设计竞赛A - Anagram

xiaoxiao2021-02-28  24

Anagram

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

        Orz has two strings of the same length: A and B. Now she wants to transform A into an anagram of B (which means, a rearrangement of B) by changing some of its letters. The only operation the girl can make is to “increase” some (possibly none or all) characters in A. E.g., she can change an 'A' to a 'B', or a 'K' to an 'L'. She can increase any character any times. E.g., she can increment an 'A' three times to get a 'D'. The increment is cyclic: if she increases a 'Z', she gets an 'A' again.        For example, she can transform "ELLY" to "KRIS" character by character by shifting 'E' to 'K' (6 operations), 'L' to 'R' (again 6 operations), the second 'L' to 'I' (23 operations, going from 'Z' to 'A' on the 15-th operation), and finally 'Y' to 'S' (20 operations, again cyclically going from 'Z' to 'A' on the 2-nd operation). The total number of operations would be 6 + 6 + 23 + 20 = 55. However, to make "ELLY" an anagram of "KRIS" it would be better to change it to "IRSK" with only 29 operations.  You are given the strings A and B. Find the minimal number of operations needed to transform A into some other string X, such that X is an anagram of B.

Input

        There will be multiple test cases. For each test case:        There is two strings A and B in one line.∣A∣=∣B∣≤50 |A| = |B| \leq 50A=B50. A and B will contain only uppercase letters from the English alphabet ('A'-'Z').

Output

        For each test case, output the minimal number of operations.

Sample Input

ABCA BACA ELLY KRIS AAAA ZZZZ

Sample Output

0 29 100

Hint

Source

题目大意:

        给你两个长度不超过50,长度相同的并且仅由大写字母组成的两个字符串str1和str2。问你能否将str1中部分字符往后移位(即‘E’后移3位变为‘H’,‘Y’后移3位变为‘B’,26个字母的移位操作是循环的,即‘Z’后移为‘A’),且每个字符只能往后移位!!!变为str2中的字符。问你最少移多少位可以使str1变为str2。不要求字符下标对应相等。只保证str1移位后成为str2的重组字符串即可。

        妈耶,这题目大意总结的,我都觉得别扭,文采就这了,希望看到的能理解。

解题思路:

        既然是纯大写字母,并且只能向后移位,那么直接打表一个移位字符数组ans,查询移位量时,遍历字符数组。比如查询‘L’变为‘R’的移位量,先在ans数组中找到第一次出现‘L’的下标t1=12,再从这个下标t1开始往后遍历第一次出现‘R’的下标t2=18,t2-t1=6即‘L’到‘R’的移位量。移位量的计算操作实现了,接下来求最小移位量。

        题目只要求str1移位之后是str2的重组字符,所以下标无所谓,那么将两个字符串从小到大sort排序,相同下标对应的字符最接近。但因为只能往后移位,那么最接近的字符不一定移位量最小。好比‘Y’与‘W’同一下标。但‘Y’到‘W’的位移量为24。怎么解决?  因为数据量小,将str2字符串向后复制一次。那么str1就可以移位为str2的任意一段重组字符。每种情况遍历一次,取最小的移位量。

        对于第2组测试数据,“ELLY”与“KRIS”。将两个数组排序之后为“KLLY”与“IRSK”。将“IRSK”复制一倍变为“IRSKIRSK”然后遍历“KLLY”分别移位为“IRSKIRSK”,“IRSKIRSK”,“IRSKIRSK”,“IRSKIRSK”(加下划线加粗的一段字符串)。取最小的移位量。

        具体看代码。

不知道严谨不严谨的AC代码:

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; char str1[60], str2[120]; char ans[60] = {"#ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ"}; int main() { while( ~scanf("%s%s",str1,str2) ) { int len = strlen(str1); sort(str1,str1+len); sort(str2,str2+len); for( int i = len; i < 2*len; i++ ) str2[i] = str2[i-len]; int minn = 999999; for( int i = 0; i < len; i++ ) { int vis = 0; for( int j = 0; j < len; j++ ) { int t1 = 0, t2 = 0; while( ans[t1] != str1[j] ) t1++; t2 = t1; while( ans[t2] != str2[i+j] ) t2++; vis += t2 - t1; } minn = min(minn,vis); } printf("%d\n",minn); } return 0; }
转载请注明原文地址: https://www.6miu.com/read-2650135.html

最新回复(0)