uva 10716 - Evil Straw Warts Live

简介: 点击打开链接uva 10716 题目意思:  给定一个字符串求出最小需要几步交换(只有相邻才能够交换)能够变成回文串,如果不能构成回文串就输出Ipossbile 解题思路:    1:贪心 2:对于给定的字符串,如果要使得转化...

点击打开链接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;
}


目录
相关文章
|
8月前
|
人工智能 BI
UVA live 2678 - Subsequence
关于这个题目,有多种的解法,如果枚举起点和终点,时间复杂度为O(n^3),但如果我们用一个数组B把一段数的和存起来,B[i] = sum(a[1].....a[i])。这样就可以把时间复杂度降到O(n^2)。
34 0
uva live 3516 - Exploring Pyramids
点击打开链接 题意:给出一棵多叉树,每个结点的任意两个子节点都有左右之分。从根节点开始,每次尽量往左走,走不通就回溯,把遇到的字母顺序记录下来,可以得到一个序列。
746 0
|
API C++ Windows
【Live555】Live555 Windows下使用VS2017编译教程
【Live555】Live555 Windows下使用VS2017编译教程
【Live555】Live555 Windows下使用VS2017编译教程
|
数据建模 C++ Windows
live555开发笔记(一):live555介绍、windows上msvc2017编译和工程模板
live555开发笔记(一):live555介绍、windows上msvc2017编译和工程模板
live555开发笔记(一):live555介绍、windows上msvc2017编译和工程模板