NC15927. Anagram
描述
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.
输入描述
There will be multiple test cases. For each testcase:
There is two strings A and B in one line.∣A∣=∣B∣≤50. A and B will contain only uppercase letters
from the English alphabet (‘A’-‘Z’).
输出描述
For each test case, output the minimal number of
operations.
示例1
输入:
ABCA BACA ELLY KRIS AAAA ZZZZ
输出:
0 29 100
Python3(3.5.2) 解法, 执行用时: 61ms, 内存消耗: 3568K, 提交时间: 2020-02-20 19:46:58
while True:
try:
a, b = map(list, input().split())
except EOFError:
break
a.sort()
b.sort()
l = len(a)
ans = 26*l
for k in range(0, l):
j = k
sum = 0
for i in range(0, l):
sum += (ord(b[j])-ord(a[i])+26) % 26
i += 1
j += 1
j %= l
ans = min(ans, sum)
print(ans)
C++(clang++11) 解法, 执行用时: 3ms, 内存消耗: 472K, 提交时间: 2021-04-26 20:42:26
#include<bits/stdc++.h>
using namespace std;
int main(){
string a,b;
while(cin>>a>>b){
int s=0,l=a.length();
int s1=0,s2=l-1;
sort(a.begin(),a.end());
sort(b.begin(),b.end());
for(int i=0;i<l;i++){
if(a[s1]<=b[i]){
s+=b[i]-a[s1++];
}else{
s+=26-(a[s2--]-b[i]);
}
}
cout<< s<<endl;
}
return 0;
}