基础练习完美的代价（蓝桥杯字符串问题）

迷南。 2022-06-06 10:28 173阅读 0赞

首先我们知道了如何交换位置，只能相邻才能交换。

用两个循环，一个从左边，一个从右边开始遍历，分两种情况：  
①如果左边字符等于右边字符，说明，这个字符是成对的（目前），然后利用下标计算出需要移动的距离（与移动次数相等），**记录下来**，然后遍历把每个字符的位置往前移动一个位置，更新字符串，变成移动后的样子  
②判断两个循环是否相遇，如果相遇说明，需要匹配的字符不存在，  
如果字符长度为偶数，直接Impossible，  
如果不是偶数，记录这一次，如果达到第二次，那么也不可能是完美字符串，  
如果以上都没有发生，那么需要记录这个字符移动到中间位置的距离，注意这个字符是不需要真正移动的，因为我们可以略过去，不影响以后的计算，以为以后的计算都是两点的距离，与开头结尾的位置无关。

例如字符串  
**macmacd**  
12345678  
m与d不同，m与c不同，最终到了m与m，1位置和4位置，4-1=3，移动三次，维护字符串为  
macmacdm  
下一次循环的时候就从a与d比较开始，缩短比较的长度

#include<iostream> 
    
    using namespace std;
    
    int main() {
        int n, len, flag = 0, index, ans = 0;
        char str[8005];
        cin >> len;
        cin >> str+1;
        n = len;//记录初始长度 
        for(int i = 1; i <= n; i++) {
            for(int j = n; j >= 1; j--) {
                if(i == j) {
                    flag++;//记录次数 
                    if(len%2==0 || flag > 1) {
       //如果有一次并且是偶数长度，肯定不行，flag==2，说明有两次，奇数个数也不行 
                        cout << "Impossible" << endl;
                        return 0;
                    } 
                    index = len/2 - i + 1;//移动到中间位置的步数 
                    break;
                }
                else if(str[i] == str[j]) {
                    ans += n - j;//移动的距离 
                    for(int l = j; l < n; l++) {
                        str[l] = str[l+1];//往前移动 
                    }
                    str[n] = str[i];//维护字符串为移动后 
                    n--;//略过已经移动好的，下一次遍历就从没有判定的地方开始 
                    break;
                }
            }
        }
        cout << ans+index << endl;
        return 0;
    }