[蓝桥杯][基础练习VIP]完美的代价

题目

题目链接

题解

1. Impossible的情况：当字符串长度为偶数时，不能存在出现次数为奇数次的字符，而且若出现则必然出偶数个“出现次数为奇数次”的字符，即出现次数为奇数次的字符的个数>1；当字符串长度为奇数时，必然存在一个字符出现次数为奇数。因此两种情况可以统一为：若出现次数为奇数次的字符的个数>1，则Impossible。
2. 将字符串分为两半，对于在左半边遍历到的字符，我们去右半边从右向左找（右半边遍历的起点为左侧当前字符关于中心位置对称过去的位置，右半边遍历的终点为左侧当前字符的后一个位置，即无法到达左侧当前字符），找到第一个与左边遍历的当前字符一样的右边字符，我们就让找到一致字符位置到右半边遍历的起点处从左至右顺次交换，统计交换次数。
3. 特殊情况，当存在孤立字符在左半边时（孤立字符就是在字符串长度为奇数时存在的出现次数为奇数的字符），我们跳过它，先不让它进行交换，而是等全部其他的字符都完成了交换后，再让它直接交换到中心即可，这样是防止假如它提前移动到中心，之后的一些交换操作若跨越了中心，那么必然会增加交换的次数。跳过它之后，我们右半边遍历的起点还要保持为上一个位置，也就是说从遇到孤立字符之后遍历的左半边字符对应于右半边查找的起点不再是关于中心对称的了，而是关于中心的对称位置再+1（不理解可见下图），之后的操作还是与“2”中描述的是一样的。

这是上面"3"所描述的问题： 当遇到孤立字符p，p对应的搜索应当从右侧的d开始，但是p不进行搜索，因此左侧的d就还是从右侧的d开始搜起。

其他大佬模拟的一个过程，这是对应于上面“2”的描述： 对应于上面“3”的描述：

代码

#include
using namespace std;

int n, ans, cnt[26], ccnt, flag; // flag用于控制是否遇到过孤立字符了 
//int rit; // 另一种方式控制右侧遍历的起点 
string s;

int findd(int r, int l, char c) { // 此函数用于从右侧向左侧找到第一个与目标一样的字符，参数名就是其含义 
	for(int i = r;i > l;i --) if(s[i] == c) return i;
	return -1; // 没找到返回-1 
}

int change(int r, int l) { // 此函数用于实现交换，将字符串修改成交换后的样子 
	char c = s[l];
	for(int i = l;i >n>>s;
	// 将 Impossible 的情况判出去 
	for(int i = 0;i