CodeForces 1015B-Obtaining the String

不念不忘少年蓝@ 2022-05-17 11:53 151阅读 0赞

*  # CodeForces 1015B-Obtaining the String #

--------------------

*  ## 题目链接：[B. Obtaining the String][] ##
 *  ## 思路： ##

题目大意是给两个字符串，对串1某相邻两个字符进行交换，直到两个字符相等，输出交换次数及交换的下标i

我是定住了串2，然后**查找串2对应位置的字符在串1中的位置**，**如果两个位置是相等的，那么不需要进行操作，串2下标+1**，**如果不相等，每次将查找到的字符与前一个字符进行交换，保存查找字符的下标，*直到该字符下标与串2下标的字符相等，串2下标+1，进行下一次匹配***

看下样例和提示

**6  
abcdef  
abdfec**

**4  
3 5 4 5**

**Node："abcdef" →→ "abdcef" →→ "abdcfe" →→ "abdfce" →→ "abdfec".**

*  ## 代码： ##

#include<iostream>
    #include<string>
    using namespace std;
    #define MAX_SIZE 100005
    string Str1,Str2;
    int Res[MAX_SIZE];
    int Len;
    int main()
    {
        cin>>Len;
        cin>>Str1>>Str2;
        int Path=0;
        int i=0,j;
        int Break_Flag=0;
        while(i<Str2.size())
        {
            for(j=i;j<Str2.size();j++)
                if(Str2[i]==Str1[j])
                    break;
            if(j>=0&&j<Str2.size())   //find
            {
                if(j!=i)
                {
                    Res[Path++]=j;
                    char Temp=Str1[j];
                    Str1[j]=Str1[j-1];
                    Str1[j-1]=Temp;
                    //cout<<Str1<<endl;
                    if(Str1[i]==Str2[i])
                        i++;
                }
                else
                    i++;
            }
            else
            {
                Break_Flag=1;
                break;
            }
        }
        if(Break_Flag)
            cout<<"-1"<<endl;
        else
        {
            cout<<Path<<endl;
            for(i=0;i<Path;i++)
            {
                if(i)
                    cout<<" "<<Res[i];
                else
                    cout<<Res[i];
            }
        }
        return 0;
    }

[B. Obtaining the String]: http://codeforces.com/problemset/problem/1015/B