拼多多0515 笔试第三题

3、多多的字符翻转

多多君在研究十六进制字符串的翻转关系，每次可以选择字符串中的某个子串，进行一次整体变大或变小的翻转。例如: "ABCD"选择中间2个字符的子串"BC"，变大翻转会变成: "ACDD"，变小翻转会变成:"AABD"。特别的，字符0'变小的翻转会变成字符F'，同理字符'F'的变大翻转会变成字符0'，以此循环往复。多多君想知道，给定两个字符串A和B，最少可以用多少次翻转使得字符串A变成字符串B。

输入描述

第一行，1个整数T，代表测试用例的组数。( 1 <=T<= 1,000 ) 对于每一组测试用例，共一行:2个字符串A和B。(两个字符串由数字或大写的字母组成，数据保证两个字符串长度相同，并且不超过4)

输出描述

对于每组测试用例，输入一行，一个整数，表示字符串A翻转成字符串B的最少步数。

示例1

输入

5
AB BC
01 F0
ABCD BDEE
AAA FFF
0AF ABC

输出

1
1
2
5
10

思路

首先B串的每个字符减去A串对应的每个字符，如：

AB BC 可以得到1、1
01 F0 可以得到-1、-1
ABCD BDEE 可以得到 1、2、2、1
AAA FFF
0AF ABC

然后对得到的序列遍历，翻转，使得最后为全0，如：

1、1 同时减去1 得到全0
-1、-1 同时加1 得到全0
3、5、2、4 先同时减2，得到新的序列 1、3、0、2，再对前两个同时减1，得到0、2、0、2，再分别对第二个和第四个同时减去2，因此翻转次数为：2+1+2+2

#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
using namespace std;
unordered_map<char, int> mmap = {{'0',0},{'1',1},{'2',2},{'3',3},{'4',4},{'5',5},{'6',6},{'7',7},{'8',8},
	{'9',9},{'A',10}, {'B',11},{'C',12}, {'D',13}, {'E',14}, {'F',15}};

int helper(string& A, string& B) {
	vector<int> vec(4);
	int n = A.size();
	for (int i = 0; i < n; i++) {
		vec[i] = mmap[B[i]] - mmap[A[i]] > 8 ? mmap[B[i]] - mmap[A[i]] - 16 : mmap[B[i]] - mmap[A[i]];
	}
	int count = 0;
	for (int i = 0; i < 4; i++) {
		while (vec[i] != 0) {
			//小于0
			if (vec[i] < 0) {
				int t_max = vec[i];
				int j;
				for (j = i + 1; j < 4; j++) {
					if (vec[j] >= 0) {
						break;
					}
					else {
						t_max = max(t_max, vec[j]);
					}
				}
				for (int z = i; z < j; z++) {
					vec[z] += abs(t_max);
				}
				count += abs(t_max);

			}
			//大于0
			else {
				int t_min = vec[i];
				int j;
				for (j = i + 1; j < 4; j++) {
					if (vec[j] <= 0) {
						break;
					}
					else {
						t_min = min(t_min, vec[j]);
					}
				}
				for (int z = i; z < j; z++) {
					vec[z] -= t_min;
				}
				count += t_min;

			}
		}
	}
	return count;
}
int main() {
	string A, B;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> A >> B;
		cout << endl;
		cout << helper(A, B) << endl;

	}
	return 0;
}