【错误题解】蓝桥杯VIP基础-完美的代价

basic-19.cpp

/*
题目链接：https://www.dotcpp.com/oj/problem1467.html
注意！这是错误题解，有一个测试例可以造成死循环：
7
ewfwsea
*/
#include <cstdio>
#include <vector>

using namespace std;

int main()
{
    int strLen; // 字符串长度
    scanf(" %d", &strLen);
    vector<char> myStr(strLen); // 根据长度初始化字符vector长度
    char temp;
    for (int i = 0; i < strLen; i++)
    { // 从标准输入读入字符, 忽略前面的空白符\n
        scanf(" %c", &temp);
        myStr[i] = temp;
    }
    // 字符串长度是否是奇数
    bool isOdd = strLen & 1;
    // 【落单】的字符的位置，对于【奇数长】的回文串中，有且仅能有一个不成对的字符，比如acbca中的b
    int aloneCharPos = -1;
    // 字符串中间一位的下标
    int middleInd = (strLen - 1) / 2;
    // 纪录交换次数
    int swapCount = 0;
    // 开始处理字符串
    // former最先选中一个字符
    /*
        former从第0个字符扫描到字符串中间的一位
        为什么只用到中间? 我经过多次实践才得出这个推论：
            💡在交换相邻字符的时候，
                - 如果右半侧【有两个相同的字符】，总会至少有【其中一个】被“挤”到左侧
                - 而如果右半侧有【一个落单的字符】，它则总会被“挤”到正中心
    */
    for (int former = 0; former <= middleInd; former++)
    {
        int destInd = strLen - 1 - former; // 算出和former对称的下标，也就是要将latter的字符一直交换到下标为destInd
        // 如果和former对称的下标destInd指向的字符也是一致的，已经配对了，就不用接着往下了
        if (myStr[former] == myStr[destInd])
            continue;

        int latter = -1;
        // 找到一个【和former对应的字符相同的字符】，i从former的下一位开始扫描到字符串尾部
        for (int i = former + 1; i < strLen; i++)
        {
            if (myStr[former] == myStr[i])
            {
                int symmetry = strLen - 1 - i; // 算出与i下标对称的下标
                /*
                    比如aabba, 如果former指向的是第二个a, i此时会等于最后一个a的下标，
                    但是这个a已经和第一个a对称了，这个时候就需要跳过了。
                    💡 值得注意的是，i=symmetry的时候指向正中间的字符，比如mamad中的第二个m，允许这种情况
                */
                if (i == symmetry || myStr[i] != myStr[symmetry])
                {
                    latter = i; // 找到了相同的字符
                    break;
                }
            }
        }
        // latter如果还是-1，说明没找到与former相同的字符, former指向的这个字符【落单了】
        if (latter == -1)
        {
            // 对于【落单字符】的处理
            // 在【回文串长度为奇数】时，有且仅能有【一个落单字符】，或者扫描到的这个字符【已经被标记为落单字符】
            if (isOdd && aloneCharPos == -1)
            {
                // 唯一的落单字符【只能在回文串的最中间】, 所以将终点下标destInd设为middleInd
                destInd = middleInd;
                latter = former;          // 将latter指向former，也就是指向【这个落单的字符】
                aloneCharPos = middleInd; // 【落单字符】接下来肯定会被移动到正中间，因此记录落单字符下标为middleInd
                former--;                 // 💡 former需要回退，因为改变了former所指向的字符，需要重新扫描一次former这个字符
            }
            else
            {
                // 其他情况，那就不可能形成回文串了，程序结束
                printf("Impossible");
                return 0;
            }
        }
        // 接下来将latter指向的字符【不停地与相邻字符(latter+1所指)交换】，直至达到destInd
        for (; latter < destInd; latter++)
        {
            int nextInd = latter + 1; // latter要和nextInd下标交换字符
            char temp = myStr[nextInd];
            myStr[nextInd] = myStr[latter];
            myStr[latter] = temp;
            // 💡 如果移动的是落单字符的位置，需要更新aloneCharPos
            // 比如accbdda中的b是落单的，aloneCharPos=3。
            // 但是在移动第二个c后变成了acbddca，这个时候aloneCharPos要更新成2
            if (nextInd == aloneCharPos)
                aloneCharPos = -1; // 落单字符前移，aloneCharPos重置，因为会重新扫描到落单字符
            swapCount++;           // 纪录交换次数
        }
    }
    printf("%d\n", swapCount);
    // TESING CODE
    for (int i = 0; i < strLen; i++)
        printf("%c", myStr[i]);
    return 0;
}