回文串（完美的代价）

回文串，也被称为回文字符串，是一种特殊的字符串，它正读反读都是一样的，比如"madam"、"level"或者"12321"。在本题中，我们关注的是如何通过交换字符将一个非回文串转换成回文串，并计算所需的最小交换次数。 我们需要理解问题的核心：给定一个字符串，如何检查它是否是回文串。对于这个问题，我们可以从字符串的两端开始，依次比较字符是否相同。如果在任何时候发现两个相对的字符不相等，那么该字符串就不是回文串。如果所有对应位置的字符都相等，那么字符串就是回文串。 在C++中，我们可以使用以下算法来检查回文串： ```cpp #include <iostream> #include <string> bool isPalindrome(std::string str) { int left = 0; int right = str.size() - 1; while (left < right) { if (str[left] != str[right]) { return false; } left++; right--; } return true; } ``` 接下来，我们要处理非回文串的情况。为了将其转换为回文串，我们可以尝试交换不匹配的字符对。为了找到这些字符对并计算交换次数，我们可以遍历字符串，记录下每个字符的位置及其出现次数。同时，我们需要关注奇数位置的字符，因为回文串的中心可能有奇数个字符。 ```cpp #include <unordered_map> int countSwaps(std::string str) { std::unordered_map<char, int> charCount; int oddPosChar = 0; for (int i = 0; i < str.size(); ++i) { charCount[str[i]]++; if (i % 2 != 0) { oddPosChar++; } } // 回文串的中心最多有一个奇数字符 int swaps = std::max(oddPosChar - 1, 0); for (const auto &pair : charCount) { if (pair.second % 2 != 0) { swaps += pair.second / 2; } } return swaps; } ``` 在上述代码中，`countSwaps`函数首先统计了每个字符的出现次数，然后计算了奇数位置字符的数量。由于回文串的中心最多只能有一个奇数字符，所以超出这个数量的字符都需要进行一次交换。对于出现次数为奇数的字符，它们的一半需要与其它字符交换以达到回文状态。 结合这两个函数，我们可以编写一个完整的程序，接收用户输入的字符串，判断它是否已经是回文串，如果不是，则计算转换为回文串所需的最小交换次数，并打印出步骤数。 ```cpp int main() { std::string input; std::getline(std::cin, input); // 转换为小写 std::transform(input.begin(), input.end(), input.begin(), ::tolower); if (isPalindrome(input)) { std::cout << "输入的字符串已经是回文串。" << std::endl; } else { int swaps = countSwaps(input); std::cout << "通过交换字符可以将字符串转换为回文串，需要的最小交换次数为：" << swaps << "次。" << std::endl; } return 0; } ``` 在这个程序中，我们先将输入的字符串转换为小写，确保大小写不影响回文的判断。然后，根据`isPalindrome`和`countSwaps`的结果，给出相应的输出。 在VS 2008环境下编译运行此程序，你可以输入任意字符串，它将告诉你这个字符串是否是回文，如果不是，将给出转换为回文串的最小交换次数。这就是利用C++解决“回文串（完美的代价）”问题的基本思路。