【ICPC-101】uva 10716 - Evil Straw Warts Live

点击打开链接uva 10716

 

题目意思： 

给定一个字符串求出最小需要几步交换（只有相邻才能够交换）能够变成回文串，如果不能构成回文串就输出Ipossbile

 

解题思路：   

1:贪心
2:对于给定的字符串，如果要使得转化次数最少，那么要求每一步都能够达到最优，那么这就涉及到贪心的思想；
   1首先先判断当前的字符串是否满足回文串的性质即个数为奇数的字母 <=1 个，所以我们应该先判断是不是
     够转化为回文串
   2我们从字符串的两端同时出发，假设左端的下表为L，右端为R；
   3那么如果ch[L]=ch[R]直接跳过因为没有影响，否则我们同时在两边找到能够使得ch[L] = ch[R]的最小的步数；
   4例如cmdmcd,开始L=0，R=4，ch[0]!=ch[4],所以开始查找使得ch[0]=ch[4]的步数；如果满足ch[0] = ch[4] = 'c',  
     那么就要1步(右端c-d交换)；如果要使得ch[0] = ch[4] = 'd',那么就要2步(左端d-m-c交换)，所以我们选择步数
     小的；直到L >= R时候就说明已经交换完毕
   5注意:1一开是始我是从两端向中间交换，例如cmdmcd中右端的d-c-m，可恶的是这样竟然过了N多样列啊，然后
     贡献了好多次WA。后来改成了从中间向两边交换就是上面的cmdmcd右端的(m-c-d)，然后妥妥的A了；
     2交换的时候如果两个待交换的字母相同其实是不用交换的，所以ans应该减减

 

代码：

 

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define MAXN 110

int t , ans;
int  num[26];
char ch[MAXN];

/*判断能不能转化为回文串*/
bool judge(){
    int i , cnt;
    memset(num , 0 , sizeof(num));
    for(i = 0 ; i < strlen(ch) ; i++)
        num[ch[i]-'a']++;
    for(i = 0 , cnt = 0 ; i < 26 ; i++){
        if(num[i]%2 && num[i]) cnt++;
    }
    if(cnt > 1) return false;
    return true;
}

void solve(){
    if(!judge()){
        printf("Impossible\n");
        return;
    }
    else{
        int i , j , l ,r , l_pos , r_pos;
        ans = 0 ; l = 0 ; r = strlen(ch)-1;
        while(l < r){/*循环条件*/
            if(ch[l] != ch[r]){
                r_pos = l_pos = 0XFFFFFFF;/*初始化为无穷大*/
                for(i = l+1 ; i < r; i++){/*找到左边的字母能够满足ch[l]=ch[r]*/
                    if(ch[i] == ch[r]){
                        l_pos = i-l ; break;/*l_pos记录左边需要几步*/
                    }
                }
                for(i = r-1 ; i > l; i--){/*找到右边的字母能够满足ch[l]=ch[r]*/
                    if(ch[i] == ch[l]){
                        r_pos = r-i ; break;/*r_pos记录右边需要几步*/
                    }
                }
                if(r_pos < l_pos){/*右边步数小*/
                    ans += r_pos;
                    for(j = r-r_pos ; j < r ; j++){/*从中间向右边交换*/
                        swap(ch[j] , ch[j+1]);
                        if(ch[j] == ch[j+1]) ans--;/*如果两个相等实际上可以不用交换，ans--*/
                    }
                }
                else{/*左边步数小*/
                    ans += l_pos;
                    for(j = l+l_pos ; j > l ; j--){/*从中间向左边交换*/
                        swap(ch[j] , ch[j-1]);
                        if(ch[j] == ch[j-1]) ans--;/*如果两个相等实际上可以不用交换，ans--*/
                    }
                }
            }
            if(ch[l] == ch[r]){
                l++ ; r-- ;
            }
        }
    }
    printf("%d\n" , ans);
}

int main(){
    //freopen("input.txt" , "r" , stdin);
    scanf("%d%*c" , &t);
    while(t--){
        scanf("%s" , ch);
        solve();
    }
    return 0;
}