计分板-2021安徽省机器大赛程序设计赛道

题目描述

Alice 和 Bob 在玩游戏，两个人分别有一个计分板，记录各自的得分。得分 X 的 字典序严格小于得分 Y，那么就认为得分 X 高于得分 Y。Bob 想要自己的分数高 于 Alice，他选择了自己计分板中一些相邻位置交换。为了不让 Alice 发现，Bob 必须交换尽量少的次数，请写一个程序帮助 Bob。

输入

第一行一个字符串，表示 Bob 的得分，第二行一个字符串，表示 Alice 的得分。 字符串长度均不超过 100，只含小写英文字母。

输出

输出一行，表示最少交换次数。如果无解输出-1。

这个题目本身是不难的，从题目中可以得知bob的字符串是不动的，我们只需要改动alice的字符串使其字典序小于前者。由于字典序是从第一个字母开始比较，所有我们很容易想到用一个循环遍历bob的字符串。我们需要alice的字符串比bob的小，那么就要使alice的字符串从第一个字母开始就要等于或者小于bob的字符串。那么就很明确了，在上文所提到的循环中再遍历alice的字符串寻找对应的字符并移动它使其满足条件。但是在实际操作时我们会发现问题在于我们遍历alice的字符串时如果有和当前bob相同的字符时就停下返回了，我们并不知道后续字符串中有没有比bob当前的字符还要小的字符，也就是我们在操作时要在大循环中再加一个小循环，寻找是否有上述情况的存在，如果有则记录次数，并在循环完成后与其他情况比较。

那么核心部分的伪代码就如下所示：

for（...)  //遍历bob的字符串
{
   for(...)//遍历alice的字符串
   {
     if 相等，移动字符，并记录次数
     if 小于，记录次数，直接返回次数，程序结束
   }
   检测是否一个遍历结束后没有找到对应的字符，也就是alice的字符串中没有比当前遍历到的bob的字符
   大的字符，那么直接返回-1即可。
}

剩下的事情就是考虑极端情况和特殊情况了，比如alice的字符串或者bob的字符串为空这种极端情况，又或者“abc” 和“abcde”这种或者“acb”和“abc”这种特殊情况。解决了这些问题后程序就写好了。

int scoreboard(string a, string b)
{
	int count = 0,i,j;
	bool c = false;
	vector<int> v;
	string temp;
	if (!a.size() || !b.size())//极端情况
		return -1;
	for (j = 0; j < b.size(); j++)
	{
		for (i = j; i < a.size(); i++)
		{
			if (a[i] < b[j])
				v.push_back(count + i - j);
		}
		for (i = j; i < a.size(); i++)
		{
			if (a[i] == b[j])
			{
				count += i - j;//记录次数
				temp = a[i];
				a.erase(i, 1);
				a.insert(j, temp);//移动字符，模拟相邻两个字符交换的情况
				break;
			}
			else if(a[i]<b[j])
			{
				v.push_back(count + i - j);
				c = true;
				break;
			}
		}
		if (c)break;
		if (i == a.size() && j < a.size())//alice的字符串中找不到所对应的字符
			return -1;
		else if (i == a.size() && j >= a.size())//此处是为了处理类似“abc”和“abcde”的情况的，这时大循环还在，但小循环已经结束了
			return count;
	}
	sort(v.begin(), v.end());
	if (v.empty())
		return -1;
	else
		return v.front();
}