题目

题目C：favorite school

时间限制：1000ms 内存限制：256mb 栈限制：256mb

题目描述

胡校最爱的就是“JKFZ"（江科附中），给定一个仅包括J,K,F,Z四个字母的字符串，希望你能够通过三种操作使其变为“JKFZ"，输出最小操作次数，无解则输出-1

三种操作：

1.删除开头的字母

2.删除结尾的字母

3.交换字符串中的两个字母

输入描述

第一行一个整数T

接下来T行分别有一个字符串

输出描述

输出T行答案

样例1

样例输入

1 JKFZZ

样例输出

1

样例1解释

删除最后一个字母Z

样例2

样例输入

2 JKF KJZF

样例输出

-1 2

样例2解释

只有3个字符，无解，则输出-1 交换J与K，F与Z，两次操作

【数据范围】

保证所有$1 \leq T \leq 100$ 保证每个字符串长度n小于$10^4$

特殊性质：

A. $1 \leq n \leq 4$

B. $T = 1$

这是我的代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
string s; int len;
int T, ans;
char goal[4] = {'J', 'K', 'F', 'Z'};
unordered_map <char, char> dif;//未归位的位置应有的字母
char diff[5];//未归位
int cnt;

int check(string s){
	int len = s.length(), res = len - 4, ans = res;
	int ch[5] = {};
	dif.clear(); cnt = 0; memset(diff, 0, sizeof(diff));
	if(res < 0) return -1;
	for(int i = 0; i < len; i++){
		if(s[i] == 'J') ch[1]++; 
		if(s[i] == 'K') ch[2]++; 
		if(s[i] == 'F') ch[3]++; 
		if(s[i] == 'Z') ch[4]++; 
	}
	if(ch[1] < 1 || ch[2] < 1 || ch[3] < 1 || ch[4] < 1) return -1;
	
	int mina = N;
	for(int i = 0; i <= len - 4; i++){
		res = ans, cnt = 0;
		for(int j = 0; j < 4; j++){
			if(s[i + j] != goal[j]){
				dif[s[i + j]] = goal[j];
				++cnt, diff[cnt] = s[i + j];	//F->
				//两个相同是否需要分编号 ZKKKJF(K) FKJJZ(F, J); JKZF JKFZ JFZK
			}
		}
		if(cnt == 0) return res;
		else if(cnt == 1) res++;
		else if(cnt == 2){
			//if((dif[diff[1]] == diff[2] && dif[diff[2]] == diff[1])) res++;
			//JKZF举例，Z在的位置的应有值为F，Z在的位置的应有值的F位置的应有值为Z
			if(dif[dif[diff[1]]] == diff[1]) res++;
			else res += 2;
		}else if(cnt == 3){
			if((dif[dif[dif[diff[1]]]] == diff[1]) || (dif[dif[diff[1]]] == diff[1] || dif[dif[diff[2]]] == diff[2] || dif[dif[diff[3]]] == diff[3])) res += 2;
			else res += 3;
		}else if(cnt == 4){
			//cout << " " << (dif[dif[dif[dif[diff[1]]]]] == diff[1]) << " " << (dif[dif[dif[diff[1]]]] == diff[1]) << " " << (dif[dif[dif[diff[2]]]] == diff[2]) << " " << (dif[dif[dif[diff[3]]]] == diff[3]) << " " << (dif[dif[dif[diff[4]]]] == diff[4]) << endl;
			if(dif[dif[diff[1]]] == diff[1] || dif[dif[diff[2]]] == diff[2] || dif[dif[diff[3]]] == diff[3] || dif[dif[diff[4]]] == diff[4]){	
				int a = 0;
				if(dif[dif[diff[1]]] == diff[1]) a++;
				if(dif[dif[diff[2]]] == diff[2]) a++;
				if(dif[dif[diff[3]]] == diff[3]) a++;
				if(dif[dif[diff[4]]] == diff[4]) a++;
				if(a / 2 == 1) res += 3;
				else res += 2;
			}else if((dif[dif[dif[dif[diff[1]]]]] == diff[1]) || (dif[dif[dif[diff[1]]]] == diff[1] || dif[dif[dif[diff[2]]]] == diff[2] || dif[dif[dif[diff[3]]]] == diff[3] || dif[dif[dif[diff[4]]]] == diff[4])) res += 3;
			else res += 4;
		}
		//cout << "i: " << i << " res: " << res << " cnt:" << cnt << endl; 
		mina = min(mina, res);
	}
	return mina;
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> T;
	while(T--){
		cin >> s;
		ans = check(s);
		if(ans == -1) cout << -1 << endl;
		else cout << ans << endl;
	}
	return 0;
}

这个解法的核心思想在于先判断是否有解（是否有所有字母，是否字符串长度大于等于4）4个4个往后扫，答案取min，然后先判断4个的内部是否可以通过两两调换把两个都归位，这样就可以比4个里面与一个外面的一个调换更优。这个判断是否能够调换是重点，就是看一个位置应该有的字母的位置应该有的字母是不是那一个位置应该有的字母（可能有点绕，可以留言问我），在看看里面是有多少个与目标串不符的字母，再分类讨论。 求求了，同学，帮帮忙，谢谢了！