蓝桥杯 BASIC-19 完美的代价

富文本编辑器测试，这样子似乎没有Markdown好看欸

题目

资源限制

时间限制：1.0s   内存限制：512.0MB

问题描述

　　回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。 　　交换的定义是：交换两个相邻的字符 　　例如mamad 　　第一次交换 ad : mamda 　　第二次交换 md : madma 　　第三次交换 ma : madam (回文！完美！)

输入格式

　　第一行是一个整数N，表示接下来的字符串的长度(N <= 8000) 　　第二行是一个字符串，长度为N.只包含小写字母

输出格式

　　如果可能，输出最少的交换次数。 　　否则输出Impossible

样例输入

5 mamad

样例输出

3

解题思路

    本题的主要考点是贪心算法，因此考虑最少交换次数可以看成每对元素中只有一个元素进行单向移动。具体操作是，从左边开始先固定一个元素，然后从右边开始扫描，寻找第一个相同的元素，若能找到则将该元素移动到右边相对应的位子并记录交换的次数；若一直扫描到该左边的元素自己，则说明未配对的该元素只有一个，若n为偶数则说明不是回文串，若n为奇数则先计算该元素移到中间所需的次数并在后面的移动中跳过该元素，若第二次找到不能配对的元素则说明不是回文串。

    在写本题代码时我自己遇到的几个需要注意的点：

无需将偶数与奇数情况分开讨论，n为奇数时增加一个标志位flag即可，可以使用flag来实现扫描与交换时跳过单个数的功能。可以将外循环的i范围设为0~n-1，因为当n-1-i+flag >= i时会自动跳过内循环；而一对初始位置都在中点右边出现的元素会随着其他元素的交换自动移动到中点左边，因此无需多加考虑。代码中我使用了exit()函数来退出程序，但由于蓝桥杯的系统要求main函数一定要return 0，因此若使用exit(1)则会被蓝桥杯系统判定为“运行错误”，因此一定要使用exit(0)来退出程序。

代码

#include <iostream> using namespace std; int main() { int n; int count = 0; cin >> n; string arr; cin >> arr; int flag = 0; for(int i=0; i<n; i++){ for(int j=n-1-i+flag; j>=i; j--){ //从后向前找 if(j==i) //当配对到自己时说明该元素只有一个未配对 if(n%2==0){ //偶数情况 cout<<"Impossible"<<endl; exit(0); }else{ //奇数情况 flag++; count += n/2 - i; if(flag > 1){ //超过两个元素不能配对 cout<<"Impossible"<<endl; exit(0); } break; } if(arr[i] == arr[j] && i != j){ for(int k=j; k<n-1-i+flag; k++){ swap(arr[k], arr[k+1]); count++; } break; //找到第一个相同的元素即可退出循环 } } } cout<<count<<endl; return 0; }

如有错误之处，望大佬们指正。